Expansion of gap-planar graphs
By: David R. Wood
Potential Business Impact:
Makes drawings of tricky maps with fewer crossing lines.
A graph is $k$-gap-planar if it has a drawing in the plane such that every crossing can be charged to one of the two edges involved so that at most $k$ crossings are charged to each edge. We show this class of graphs has linear expansion. In particular, every $r$-shallow minor of a $k$-gap-planar graph has density $O(rk)$. Several extensions of this result are proved: for topological minors, for $k$-cover-planar graphs, for $k$-gap-cover-planar graphs, and for drawings on any surface. Application to graph colouring are presented.
Similar Papers
Expansion of gap-planar graphs
Combinatorics
Draws pictures of connected dots with fewer messy overlaps.
Structural Parameterizations of $k$-Planarity
Data Structures and Algorithms
Helps draw complex maps with fewer line crossings.
k-Planar and Fan-Crossing Drawings and Transductions of Planar Graphs
Computational Geometry
Draws complex graphs on flat surfaces.