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:

Artikel in Zeitschriften

erschienen in:

Discrete & Computational Geometry, Vol. 71(4), pp. 1429-1455, 2024

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₅, 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. (Isr. J. Math. 46(1–2), 127–144 (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:

DOI