Edge-Minimum Saturated k-Planar Drawings

DOI10.1007/978-3-030-92931-2_1MaRDI QIDQ6356216arXivFDO

Authors Steven Chaplick, Fabian Klute, Irene Parada, Jonathan Rollin, Torsten Ueckerdt

Publication date 15 December 2020

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-92931-2_1

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

arXiv classification

cs.CGcs.DMmath.CO

Abstract: For a class $mathcalD$ of drawings of loopless (multi-)graphs in the plane, a drawing $DinmathcalD$ is emph{saturated} when the addition of any edge to $D$ results in $D^{\prime }otinmathcalD$ - this is analogous to saturated graphs in a graph class as introduced by Tur'an (1941) and ErdH{o}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 $mathcalD$ 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 $$ edges for any $kgeq4$, while if all that is forbidden, the sparsest such drawings have $frac2(k+1)k(k-1)(n-1)$ edges for any $kgeq6$.

This page was built for publication: Edge-Minimum Saturated k-Planar Drawings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6356216)