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 -quasiplanar graph admits such a graph
drawing with no
pairwise crossing edges. The case
gives planar graphs. The
edges may be curved, and two edges
may cross more than once.
Milojević et al. (2026) proved that every -quasiplanar graph on
vertices has
edges, with an absolute
implied constant. Here
denotes big-O notation.
Consequently, every graph drawing of the complete
graph
in the plane contains
pairwise crossing edges,
where
is big-omega notation. The stronger proposed
edge bound remains open. Milojević et al. (2026) report AI assistance
with the combinatorial lemma that bounds changes in successors in their charging
argument.