2020/12/15 by Chaplick, Steven, Klute, Fabian, Parada, Irene +2
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2012.08631
For a class D of drawings of loopless (multi-)graphs in the plane, a drawing D ∈ D is saturated when the addition of any edge to D results in D' ∉ D - this is analogous to saturated graphs in a graph class as introduced by Turán (1941) and Erdős, Hajnal, and Moon (1964). We focus on k-planar drawings, that is, graphs drawn in the plane where each edge is crossed at most k times, and the classes D of all k-planar drawings obeying a number of restrictions, such as having no crossing incident edges, no pair of edges crossing more than once, or no edge crossing itself. While saturated k-planar drawings are the focus of several prior works, tight bounds on how sparse these can be are not well understood. We establish a generic framework to determine the minimum number of edges among all n-vertex saturated k-planar drawings in many natural classes. For example, when incident crossings, multicrossings and selfcrossings are all allowed, the sparsest n-vertex saturated k-planar drawings have (2)/(k - (k \bmod 2)) (n-1) edges for any k ≥ 4, while if all that is forbidden, the sparsest such drawings have (2(k+1))/(k(k-1))(n-1) edges for any k ≥ 6.