zbMATH — the first resource for mathematics

On crossing numbers of geometric proximity graphs. (English) Zbl 1213.05179
Summary: Let \(P\) be a set of \(n\) points in the plane. A geometric proximity graph on \(P\) is a graph where two points are connected by a straight-line segment if they satisfy some prescribed proximity rule. We consider four classes of higher order proximity graphs, namely, the \(k\)-nearest neighbor graph, the \(k\)-relative neighborhood graph, the \(k\)-Gabriel graph and the \(k\)-Delaunay graph. For \(k=0\) (\(k=1\) in the case of the \(k\)-nearest neighbor graph) these graphs are plane, but for higher values of \(k\) in general they contain crossings. In this paper, we provide lower and upper bounds on their minimum and maximum number of crossings. We give general bounds and we also study particular cases that are especially interesting from the viewpoint of applications. These cases include the 1-Delaunay graph and the \(k\)-nearest neighbor graph for small values of \(k\).

05C62 Graph representations (geometric and intersection representations, etc.)
Full Text: DOI
[1] Abellanas, M.; Bose, P.; García, J.; Hurtado, F.; Nicolás, C.M.; Ramos, P., On structural and graph theoretic properties of higher order Delaunay graphs, Internat. J. comput. geom. appl., 19, 6, 595-615, (2009) · Zbl 1209.05199
[2] Ábrego, B.M.; Cetina, M.; Fernández-Merchant, S.; Leaños, J.; Salazar, G., 3-symmetric and 3-decomposable geometric drawings of \(K_n\), Discrete appl. math., 158, 12, 1240-1258, (2010) · Zbl 1228.05214
[3] Ábrego, B.M.; Fernández-Merchant, S.; Leaños, J.; Salazar, G., A central approach to bound the number of crossings in a generalized configuration, Electron. notes discrete math., 30, 273-278, (2008) · Zbl 1341.05035
[4] Ajtai, M.; Chvátal, V.; Newborn, M.M.; Szemerédi, E., Crossing-free subgraphs, Ann. discrete math., 12, 9-12, (1982) · Zbl 0502.05021
[5] Di Battista, G.; Eades, P.; Tamassia, R.; Tollis, I.G., Graph drawing: algorithms for the visualization of graphs, (1998), Prentice Hall
[6] Brass, P.; Moser, W.; Pach, J., Graph drawings and geometric graphs, (), 373-416
[7] Duda, R.O.; Hart, P.E.; Stork, D.G., Pattern classification, (2001), John Wiley & Sons · Zbl 0968.68140
[8] V. Dujmović, K. Kawarabayashi, B. Mohar, D.R. Wood, Improved upper bounds on the crossing number, in: Proc. SoCG’08, 2008, pp. 375-384. · Zbl 1271.05027
[9] Garey, M.R.; Johnson, D.S., Crossing number is NP-complete, SIAM J. algebra discr., 4, 312-316, (1983) · Zbl 0536.05016
[10] Gudmundsson, J.; Hammar, M.; van Kreveld, M., Higher order Delaunay triangulations, Comput. geom., 23, 85-98, (2002) · Zbl 1005.65020
[11] Guy, R.K., A combinatorial problem, Bull. malayan math. soc., 7, 68-72, (1960)
[12] Herman, I.; Melançon, G.; Marshall, M.S., Graph visualization and navigation in information visualization: A survey, IEEE T. VLSI syst., 6, 24-43, (2000)
[13] M.J. Islam, Q.M.J. Wu, M. Ahmadi, M.A. Sid-Ahmed, Investigating the performance of naive-Bayes classifiers and k-nearest neighbor classifiers, in: Proc. ICCIT’07, 2007, pp. 1541-1546.
[14] Jaromczyk, J.W.; Toussaint, G.T., Relative neighborhood graphs and their relatives, Proc. IEEE, 80, 9, 1502-1517, (1992)
[15] Jünger, M.; Mutzel, P., Graph drawing software, (2004), Springer
[16] de Klerk, E.; Pasechnik, D.V.; Schrijver, A., Reduction of symmetric semidefinite programs using the regular ⁎-representation, Math. program. ser. B, 109, 613-624, (2007) · Zbl 1200.90136
[17] van Kreveld, M.; Löffler, M.; Silveira, R.I., Optimization for first order Delaunay triangulations, Comput. geom., 43, 4, 377-394, (2010) · Zbl 1186.65025
[18] Leighton, F.T., Complexity issues in VLSI, (1983), MIT Press
[19] G. Liotta, Proximity drawings, in: Handbook of Graph Drawing and Visualization, Chapman & Hall/CRC Press, in preparation.
[20] Okabe, A.; Boots, B.; Sugihara, K.; Chiu, S.N., Spatial tessellations: concepts and applications of Voronoi diagrams, (2000), John Wiley & Sons · Zbl 0946.68144
[21] ()
[22] Pach, J.; Radoičić, R.; Tardos, G.; Tóth, G., Improving the crossing lemma by finding more crossings in sparse graphs, Discrete comput. geom., 36, 527-552, (2006) · Zbl 1104.05022
[23] Pach, J.; Spencer, J.; Tóth, G., New bounds on crossing numbers, Discrete comput. geom., 24, 623-644, (2000) · Zbl 0963.05038
[24] Pach, J.; Tóth, G., Graphs drawn with few crossings per edge, Combinatorica, 17, 3, 427-439, (1997) · Zbl 0902.05017
[25] M. Saumell, On geometric proximity, Ph.D. thesis, in preparation.
[26] Su, T.-H.; Chang, R.-Ch., The K-gabriel graphs and their applications, (), 66-75
[27] Su, T.-H.; Chang, R.-Ch., Computing the k-relative neighborhood graphs in Euclidean plane, Pattern recogn., 24, 231-239, (1991)
[28] Toussaint, G., Geometric proximity graphs for improving nearest neighbor methods in instance-based learning and data mining, Internat. J. comput. geom. appl., 15, 2, 101-150, (2005) · Zbl 1067.68166
[29] Turán, P., On an extremal problem in graph theory, Matematicko fizicki lapok, 48, 436-452, (1941)
[30] Wood, D.R.; Telle, J.A., Planar decompositions and the crossing number of graphs with an excluded minor, New York J. math., 13, 117-146, (2007) · Zbl 1120.05063
[31] Wu, Y.; Ianakiev, K.; Govindaraju, V., Improved k-nearest neighbor classification, Pattern recogn., 35, 10, 2311-2318, (2002) · Zbl 1006.68885
[32] Zarankiewicz, K., On a problem of P. Turán concerning graphs, Fund. math., 41, 137-145, (1954) · Zbl 0055.41605
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.