Veröffentlichung

Titel:

Edge-Minimum Saturated k-Planar Drawings

AutorInnen:

Steven Chaplick
Fabian Klute
Irene Parada
Jonathan Rollin
Torsten Ueckerdt

Kategorie:

Konferenzbandbeiträge

erschienen in:

Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021), Tübingen

Download:

arXiv

BibTeX-Eintrag:

@InProceedings{DBLP:journals/corr/abs-2012-08631, author = {Steven Chaplick and Jonathan Rollin and Torsten Ueckerdt}, title = {Edge-Minimum Saturated k-Planar Drawings}, journal = {CoRR}, volume = {abs/2012.08631}, year = {2020}, url = {https://arxiv.org/abs/2012.08631}, eprinttype = {arXiv}, eprint = {2012.08631}, timestamp = {Sat, 02 Jan 2021 15:43:30 +0100}, biburl = {https://dblp.org/rec/journals/corr/abs-2012-08631.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }

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 mod 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 .