Expansion of gap-planar graphs

2025/09/03 by Wood, David R.
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2509.03121

Abstract

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.

Citations

• Structure of k-Matching-Planar Graphs
• On the generalized coloring numbers
• Intersection Graphs with and without Product Structure
• Powers of planar graphs, product structure, and blocking partitions
• Treewidth, Circle Graphs and Circular Drawings
• Shallow Minors, Graph Products and Beyond Planar Graphs
• Shallow Minors, Graph Products, and Beyond-Planar Graphs
• An improved planar graph product structure theorem
• A note on sublinear separators and expansion
• Graph product structure for non-minor-closed classes
• On classes of graphs with strongly sublinear separators
• Crossing Patterns in Nonplanar Road Networks
• Structure of Graphs with Locally Restricted Crossings
• Strongly sublinear separators and polynomial expansion
• Degree-3 Treewidth Sparsifiers
• Sublinear separators, fragility and subexponential expansion
• Parameters Tied to Treewidth
• Parameters Tied to Treewidth
• Deciding first-order properties of nowhere dense graphs
• Constant-factor approximation of domination number in sparse graphs

Related

• Testing Gap k-planarity is NP-complete
• Shallow Minors, Graph Products and Beyond Planar Graphs
• The Density Formula: One Lemma to Bound Them All
• On k-planar Graphs without Short Cycles
• A first view on the density of 5-planar graphs