A Simplified Proof for the Edge-Density of 4-Planar Graphs
By: Aaron Büngener
Potential Business Impact:
Untangles messy drawings with fewer lines.
A graph on $n \ge 3$ vertices drawn in the plane such that each edge is crossed at most four times has at most $6(n-2)$ edges -- this result proven by Ackerman is outstanding in the literature of beyond-planar graphs with regard to its tightness and the structural complexity of the graph class. We provide a much shorter proof while at the same time relaxing the conditions on the graph and its embedding, i.e., allowing multi-edges and non-simple drawings.
Similar Papers
A Simplified Proof for the Edge-Density of 4-Planar Graphs
Combinatorics
Makes drawings with fewer crossings possible.
Crossing Number of 3-Plane Drawings
Combinatorics
Limits how many times lines can cross in drawings.
Unavoidable patterns and plane paths in dense topological graphs
Combinatorics
Finds hidden patterns in connected dots.