On edges crossing few other edges in simple topological complete graphs

Kynčl, Jan and Valtr, Pavel (2006) On edges crossing few other edges in simple topological complete graphs. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005, Limerick, Ireland , pp. 274-284 (Official URL: http://dx.doi.org/10.1007/11618058_25).

Full text not available from this repository.


We study the existence of edges having few crossings with the other edges in drawings of the complete graph (more precisely, in simple topological complete graphs). A {em topological graph} T=(V,E) is a graph drawn in the plane with vertices represented by distinct points and edges represented by Jordan curves connecting the corresponding pairs of points (vertices), passing through no other vertices, and having the property that any intersetion point of two edges is either a common end-point or a point where the two edges properly cross. A topological graph is {em simple}, if any two edges meet in at most one common point. Let h=h(n) be the smallest integer such that every simple complete topological graph on n vertices contains an edge crossing at most h other edges. We show that Omega(n^{3/2})le h(n) le O(n^2/log^{1/4}n). We also show that the analogous function on other surfaces (torus, Klein bottle) grows as cn^2.

Item Type:Conference Paper
Additional Information:10.1007/11618058_25
Classifications:G Algorithms and Complexity > G.420 Crossings
ID Code:697

Repository Staff Only: item control page


M. Ajtai, V. Chvatal, M. Newborn, and E. Szemeredi: Crossing-free subgraphs. Annals of Discrete Mathematics, 12 (1982), 9--12

P. Brass, W. Moser, and J. Pach: Research problems in discrete geometry. Springer (2005)

G. Cairns and Y. Nikolayevsky: Bounds for generalized thrackles. Discrete Comput. Geom., 23 (2000), 191--206

J. Cerny: Geometric graphs with no three disjoint edges. Discrete Comput. Geom. (to appear)

H. Harborth: Crossings on edges in drawings of complete multipartite graphs. Colloquia Math. Soc. Janos Bolyai, 18 (1978), 539--551

H. Harborth and M. Mengersen: Edges without crossings in drawings of complete graphs. J. Comb. Theory, Ser. B 17 (1974) 299--311

H. Harborth and M. Mengersen: Drawings of the complete graph with maximum number of crossings. Congr. Numerantium, 88 (1992), 225--228

H. Harborth and C. Thürmann: Minimum number of edges with at most s crossings in drawings of the complete graph. Congr. Numerantium, 102 (1994), 83--90

F.T. Leighton: New lower bound techniques for VLSI. Math. Systems Theory, 17 (1984), 47--70

J. Pach, R. Pinchasi, G. Tardos, and G. Tooth: Geometric graphs with no self-intersecting path of length three. Graph drawing 2002, 295--311, Lecture Notes in Comput. Sci., 2528, Springer, Berlin, 2002; also European J. Combin., 25 (2004), no. 6, 793--811

J. Pach, R Radoicic, and G. Toth: A generalization of quasi-planarity. Towards a theory of geometric graphs, 177--183, Contemp. Math., 342, Amer. Math. Soc., Providence, RI, 2004

J. Pach, R Radoicic, and G. Toth: Relaxing planarity for topological graphs. Discrete and computational geometry, 221--232, Lecture Notes in Comput. Sci. 2866, Springer, Berlin, 2003

J. Pach, J. Solymosi and G. Toth: Unavoidable configurations in topological complete graphs. Discrete Comput. Geom., 30 (2003), 311 -- 320

J. Pach and G. Toth: Disjoint edges in topological graphs. To appear

R. Pinchasi and R Radoicic:Topological graphs with no self-intersecting cycle of length 4. Towards a theory of geometric graphs, 233--243, Contemp. Math., 342, Amer. Math. Soc., Providence, RI, 2004

G. Ringel: Extremal problems in the theory of graphs. Theory Graphs Appl., Proc. Symp. Smolenice 1963, 85--90 (1964)

R.D. Ringeisen, S.K. Stueckle, and B.L. Piazza: Subgraphs and bounds on maximum crossings. Bull. Inst. Comb. Appl., 2 (1991), 33--46