Name
Abstract | ||
|---|---|---|
We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in $\\mathbb{R}^3$. 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. \r\nOur 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 $\\Omega(n \\log n)$. From the non-realizability of $K_{5,81}$, we obtain that any realizable $n$-vertex graph has $O(n^{9/5})$ edges. As such, these graphs can be considerably denser than planar graphs, but not arbitrarily dense. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.4230/LIPIcs.SoCG.2021.11 | SoCG |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 7 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Elena Arseneva | 1 | 0 | 0.68 |
| Linda Kleist | 2 | 1 | 3.06 |
| Boris Klemz | 3 | 14 | 4.11 |
| Maarten Löffler | 4 | 0 | 2.03 |
| André Schulz | 5 | 0 | 0.68 |
| Birgit Vogtenhuber | 6 | 127 | 27.19 |
| Alexander Wolff | 7 | 222 | 22.66 |