Veröffentlichung

Titel:

Adjacency Graphs of Polyhedral Surfaces

AutorInnen:

Elena Arseneva
Linda Kleist
Boris Klemz
Maarten Löffler
André Schulz
Birgit Vogtenhuber
Alexander Wolff

Kategorie:

Konferenzbandbeiträge

erschienen in:

37th International Symposium on Computational Geometry, SoCG 2021, June 7-11, 2021, Buffalo, NY, USA (Virtual Conference). LIPIcs 189, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2021

Abstract:

We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in ℝ³. We show that every graph is realizable as a polyhedral surface with arbitrary polygonal cells, and that this is not true if we require the cells to be convex. In particular, if the given graph contains K_5, K_{5,81}, or any nonplanar 3-tree as a subgraph, no such realization exists. On the other hand, all planar graphs, K_{4,4}, and K_{3,5} can be realized with convex cells. The same holds for any subdivision of any graph where each edge is subdivided at least once, and, by a result from McMullen et al. (1983), for any hypercube.
Our results have implications on the maximum density of graphs describing polyhedral surfaces with convex cells: The realizability of hypercubes shows that the maximum number of edges over all realizable n-vertex graphs is in Ω(n log n). From the non-realizability of K_{5,81}, we obtain that any realizable n-vertex graph has 𝒪(n^{9/5}) edges. As such, these graphs can be considerably denser than planar graphs, but not arbitrarily dense.

Download:

Dagstuhl

BibTeX-Eintrag:

@InProceedings{arseneva_et_al:LIPIcs.SoCG.2021.11, author = {Arseneva, Elena and Kleist, Linda and Klemz, Boris and L\"{o}ffler, Maarten and Schulz, Andr\'{e} and Vogtenhuber, Birgit and Wolff, Alexander}, title = {{Adjacency Graphs of Polyhedral Surfaces}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {11:1--11:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-184-9}, ISSN = {1868-8969}, year = {2021}, volume = {189}, editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13810}, URN = {urn:nbn:de:0030-drops-138107}, doi = {10.4230/LIPIcs.SoCG.2021.11}, annote = {Keywords: polyhedral complexes, realizability, contact representation} }