TOPICS
Search

Quasiplanar Graph


A quasiplanar graph is a simple graph that has a graph drawing in the plane with no three pairwise crossing edges (Ackerman and Tardos 2007). More generally, a k-quasiplanar graph admits such a graph drawing with no k pairwise crossing edges. The case k=2 gives planar graphs. The edges may be curved, and two edges may cross more than once.

Milojević et al. (2026) proved that every k-quasiplanar graph on n vertices has O(k^2n) edges, with an absolute implied constant. Here O denotes big-O notation. Consequently, every graph drawing of the complete graph K_n in the plane contains Omega(sqrt(n)) pairwise crossing edges, where Omega is big-omega notation. The stronger proposed O(kn) edge bound remains open. Milojević et al. (2026) report AI assistance with the combinatorial lemma that bounds changes in successors in their charging argument.


See also

Graph Drawing, Planar Graph

Explore with Wolfram|Alpha

References

Ackerman, E. and Tardos, G. "On the Maximum Number of Edges in Quasi-Planar Graphs." J. Combin. Th. Ser. A 114, 563-571, 2007. https://doi.org/10.1016/j.jcta.2006.08.002.Milojević, A.; Morawski, P.; Sudakov, B.; and Tomon, I. "Polynomial Bounds for Quasiplanar Graphs." 16 Nov 2026. https://arxiv.org/abs/2611.21416v1.

Cite this as:

Weisstein, Eric W. "Quasiplanar Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/QuasiplanarGraph.html

Subject classifications