Crossing Number of 3-Plane Drawings
By: Miriam Goetze , Michael Hoffmann , Ignaz Rutter and more
Potential Business Impact:
Limits how many times lines can cross in drawings.
We study 3-plane drawings, that is, drawings of graphs in which every edge has at most three crossings. We show how the recently developed Density Formula for topological drawings of graphs (KKKRSU GD 2024) can be used to count the crossings in terms of the number $n$ of vertices. As a main result, we show that every 3-plane drawing has at most $5.5(n-2)$ crossings, which is tight. In particular, it follows that every 3-planar graph on $n$ vertices has crossing number at most $5.5n$, which improves upon a recent bound (BBBDHKMOW GD 2024) of $6.6n$. To apply the Density Formula, we carefully analyze the interplay between certain configurations of cells in a 3-plane drawing. As a by-product, we also obtain an alternative proof for the known statement that every 3-planar graph has at most $5.5(n-2)$ edges.
Similar Papers
A Simplified Proof for the Edge-Density of 4-Planar Graphs
Combinatorics
Makes drawings with fewer crossings possible.
A Simplified Proof for the Edge-Density of 4-Planar Graphs
Combinatorics
Untangles messy drawings with fewer lines.
Sublevels in arrangements and the spherical arc crossing number of complete graphs
Combinatorics
Finds the minimum number of crossings in a drawing.