New Bounds on the Maximum Number of Edges in k-Quasi-Planar Graphs

Suk, Andrew and Walczak, Bartosz (2013) New Bounds on the Maximum Number of Edges in k-Quasi-Planar Graphs. In: 21st International Symposium, GD 2013, September 23-25, 2013, Bordeaux, France , pp. 95-106 (Official URL:

Full text not available from this repository.


A topological graph is k-quasi-planar if it does not contain k pairwise crossing edges. An old conjecture states that for every fixed k, the maximum number of edges in a k-quasi-planar graph on n vertices is O(n). Fox and Pach showed that every k-quasi-planar graph with n vertices and no pair of edges intersecting in more than O(1) points has at most n(logn) O(logk) edges. We improve this upper bound to 2α(n)cnlogn , where α(n) denotes the inverse Ackermann function, and c depends only on k. We also show that every k-quasi-planar graph with n vertices and every two edges have at most one point in common has at most O(nlogn) edges. This improves the previously known upper bound of 2α(n)cnlogn obtained by Fox, Pach, and Suk.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.420 Crossings
Z Theory > Z.750 Topology
ID Code:1364

Repository Staff Only: item control page


Ackerman, E.: On the maximum number of edges in topological graphs with no four pairwise crossing edges. Discrete Comput. Geom. 41, 365–375 (2009)

Agarwal, P.K., Aronov, B., Pach, J., Pollack, R., Sharir, M.: Quasi-planar graphs have a linear number of edges. Combinatorica 17, 1–9 (1997)

Alon, N., Spencer, J.: The Probabilistic Method, 3rd edn. Wiley Interscience (2008)

Brass, P., Moser, W., Pach, J.: Research Problems in Discrete Geometry. Springer (2005)

Capoyleas, V., Pach, J.: A Turán-type theorem on chords of a convex polygon. J. Combin. Theory Ser. B 56, 9–15 (1992)

Dilworth, R.P.: A decomposition theorem for partially ordered sets. Ann. Math. 51, 161–166 (1950)

Fox, J., Pach, J.: Coloring K k -free intersection graphs of geometric objects in the plane. European J. Combin. 33, 853–866 (2012)

Fox, J., Pach, J., Suk, A.: The number of edges in k-quasi-planar graphs. SIAM J. Discrete Math. 27, 550–561 (2013)

Klazar, M.: A general upper bound in extremal theory of sequences, Comment. Math. Univ. Carolin. 33, 737–746 (1992)

Lasoń, M., Micek, P., Pawlik, A., Walczak, B.: Coloring intersection graphs of arc-connected sets in the plane (manuscript)

McGuinness, S.: Colouring arcwise connected sets in the plane I. Graphs Combin. 16, 429–439 (2000)

McGuinness, S.: On bounding the chromatic number of L-graphs. Discrete Math. 154, 179–187 (1996)

Nivasch, G.: Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations. J. Assoc. Comput. Machin. 57, 1–44 (2010)

Pach, J., Radoičić, R., Tóth, G.: Relaxing planarity for topological graphs. In: Győri, E., Katona, G.O.H., Lovász, L., Fleiner, T. (eds.) More Sets, Graphs and Numbers, Bolyai Soc. Math. Stud., vol. 15, pp. 285–300. Springer (2006)

Pach, J., Shahrokhi, F., Szegedy, M.: Applications of the crossing number. J. Graph Theory 22, 239–243 (1996)

Pettie, S.: Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts. J. Combin. Theory Ser. A 118, 1863–1895 (2011)

Pettie, S.: On the structure and composition of forbidden sequences, with geometric applications. In: 27th ACM Symposium on Computational Geometry, pp. 370–379. ACM (2011)

Suk, A.: Coloring intersection graphs of x-monotone curves in the plane. Combinatorica (to appear)

Valtr, P.: On geometric graphs with no k pairwise parallel edges. Discrete Comput. Geom. 19, 461–469 (1998)