License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2023.31
URN: urn:nbn:de:0030-drops-178814
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17881/
Felsner, Stefan ;
Schrezenmaier, Hendrik ;
Schröder, Felix ;
Steiner, Raphael
Linear Size Universal Point Sets for Classes of Planar Graphs
Abstract
A finite set P of points in the plane is n-universal with respect to a class ? of planar graphs if every n-vertex graph in ? admits a crossing-free straight-line drawing with vertices at points of P.
For the class of all planar graphs the best known upper bound on the size of a universal point set is quadratic and the best known lower bound is linear in n.
Some classes of planar graphs are known to admit universal point sets of near linear size, however, there are no truly linear bounds for interesting classes beyond outerplanar graphs.
In this paper, we show that there is a universal point set of size 2n-2 for the class of bipartite planar graphs with n vertices. The same point set is also universal for the class of n-vertex planar graphs of maximum degree 3. The point set used for the results is what we call an exploding double chain, and we prove that this point set allows planar straight-line embeddings of many more planar graphs, namely of all subgraphs of planar graphs admitting a one-sided Hamiltonian cycle.
The result for bipartite graphs also implies that every n-vertex plane graph has a 1-bend drawing all whose bends and vertices are contained in a specific point set of size 4n-6, this improves a bound of 6n-10 for the same problem by Löffler and Tóth.
BibTeX - Entry
@InProceedings{felsner_et_al:LIPIcs.SoCG.2023.31,
author = {Felsner, Stefan and Schrezenmaier, Hendrik and Schr\"{o}der, Felix and Steiner, Raphael},
title = {{Linear Size Universal Point Sets for Classes of Planar Graphs}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {31:1--31:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-273-0},
ISSN = {1868-8969},
year = {2023},
volume = {258},
editor = {Chambers, Erin W. and Gudmundsson, Joachim},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17881},
URN = {urn:nbn:de:0030-drops-178814},
doi = {10.4230/LIPIcs.SoCG.2023.31},
annote = {Keywords: Graph drawing, Universal point set, One-sided Hamiltonian, 2-page book embedding, Separating decomposition, Quadrangulation, 2-tree, Subcubic planar graph}
}
|
Keywords: |
|
Graph drawing, Universal point set, One-sided Hamiltonian, 2-page book embedding, Separating decomposition, Quadrangulation, 2-tree, Subcubic planar graph |
|
Collection: |
|
39th International Symposium on Computational Geometry (SoCG 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
09.06.2023 |
