Document Open Access Logo

Adjacency Graphs of Polyhedral Surfaces

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

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.11.pdf
  • Filesize: 2.86 MB
  • 17 pages

Document Identifiers

Author Details

Elena Arseneva
  • Saint Petersburg State University, Russia
Linda Kleist
  • Technische Universität Braunschweig, Germany
Boris Klemz
  • Universität Würzburg, Germany
Maarten Löffler
  • Utrecht University, The Netherlands
André Schulz
  • FernUniversität in Hagen, Germany
Birgit Vogtenhuber
  • Technische Universität Graz, Austria
Alexander Wolff
  • Universität Würzburg, Germany

Funding

  • Arseneva, Elena: partially supported by RFBR, project 20-01-00488.
  • Klemz, Boris: supported by DFG project WO758/11-1.
  • Vogtenhuber, Birgit: partially supported by the Austrian Science Fund within the collaborative DACH project Arrangements and Drawings as FWF project I 3340-N35.

Acknowledgements

We thank the organizers of Dagstuhl Seminar 19352 "Computation in Low-Dimensional Geometry and Topology" for bringing us together. We are particularly indebted to seminar participant Arnaud de Mesmay for asking a question that initiated our research. We also thank the anonymous referees of our EuroCG 2020 submission for their helpful comments.

Cite AsGet BibTex

Elena Arseneva, Linda Kleist, Boris Klemz, Maarten Löffler, André Schulz, Birgit Vogtenhuber, and Alexander Wolff. Adjacency Graphs of Polyhedral Surfaces. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.11

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graphs and surfaces
  • Mathematics of computing → Combinatoric problems
Keywords
  • polyhedral complexes
  • realizability
  • contact representation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Md. Jawaherul Alam, Therese C. Biedl, Stefan Felsner, Andreas Gerasch, Michael Kaufmann, and Stephen G. Kobourov. Linear-time algorithms for hole-free rectilinear proportional contact graph representations. Algorithmica, 67(1):3-22, 2013. URL: https://doi.org/10.1007/s00453-013-9764-5.
  2. E. M. Andreev. Convex polyhedra in Lobačevskiı spaces. Mat. Sb. (N.S.), 81 (123)(3):445-478, 1970. URL: https://doi.org/10.1070/SM1970v010n03ABEH001677.
  3. Boris Aronov, Marc J. van Kreveld, René van Oostrum, and Kasturi R. Varadarajan. Facility location on a polyhedral surface. Discret. Comput. Geom., 30(3):357-372, 2003. URL: https://doi.org/10.1007/s00454-003-2769-0.
  4. Elena Arseneva, Linda Kleist, Boris Klemz, Maarten Löffler, André Schulz, Birgit Vogtenhuber, and Alexander Wolff. Adjacency graphs of polyhedral surfaces. ArXiv report, 2021. URL: http://arxiv.org/abs/2103.09803.
  5. David W. Barnette and Branko Grünbaum. On Steinitz’s theorem concerning convex 3-polytopes and on some properties of planar graphs. In G. Chartrand and S. F. Kapoor, editors, The Many Facets of Graph Theory, pages 27-40. Springer Berlin Heidelberg, 1969. Google Scholar
  6. Martin Čadek, Marek Krčál, and Lukáš Vokřínek. Algorithmic solvability of the lifting-extension problem. Discrete Comput. Geom., 57(4):915-965, 2017. URL: https://doi.org/10.1007/s00454-016-9855-6.
  7. Richard Cole and Micha Sharir. Visibility problems for polyhedral terrains. J. Symb. Comput., 7(1):11-30, 1989. URL: https://doi.org/10.1016/S0747-7171(89)80003-3.
  8. Leila de Floriani, Paola Magillo, and Enrico Puppo. Applications of computational geometry in geographic information systems. In J.R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, chapter 7, pages 333-388. Elsevier, Amsterdam, 1997. Google Scholar
  9. Hubert de Fraysseix, Patrice Ossona de Mendez, and János Pach. Representation of planar graphs by segments. Intuitive Geometry, 63:109-117, 1991. URL: https://infoscience.epfl.ch/record/129343/files/segments.pdf.
  10. Hubert de Fraysseix, Patrice Ossona de Mendez, and Pierre Rosenstiehl. On triangle contact graphs. Combinatorics, Probability and Computing, 3:233-246, 1994. URL: https://doi.org/10.1017/S0963548300001139.
  11. David P. Dobkin. Computational geometry and computer graphics. Proc. IEEE, 80:141-1, 1992. Google Scholar
  12. Christian A. Duncan, Emden R. Gansner, Yifan Hu, Michael Kaufmann, and Stephen G. Kobourov. Optimal polygonal representation of planar graphs. Algorithmica, 63(3):672-691, 2012. URL: https://doi.org/10.1007/s00453-011-9525-2.
  13. David Eppstein and Elena Mumford. Steinitz theorems for simple orthogonal polyhedra. J. Comput. Geom., 5(1):179-244, 2014. URL: https://doi.org/10.20382/jocg.v5i1a10.
  14. William Evans, Paweł Rzążewski, Noushin Saeedi, Chan-Su Shin, and Alexander Wolff. Representing graphs and hypergraphs by touching polygons in 3D. In Daniel Archambault and Csaba Tóth, editors, Proc. Graph Drawing & Network Vis. (GD'19), volume 11904 of LNCS, pages 18-32. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-35802-0_2.
  15. Stefan Felsner. Rectangle and square representations of planar graphs. In János Pach, editor, Thirty Essays on Geometric Graph Theory, pages 213-248. Springer, 2013. URL: https://doi.org/10.1007/978-1-4614-0110-0_12.
  16. Stefan Felsner and Mathew C. Francis. Contact representations of planar graphs with cubes. In Ferran Hurtado and Marc J. van Kreveld, editors, Proc. 27th Ann. Symp. Comput. Geom. (SoCG'11), pages 315-320. ACM, 2011. URL: https://doi.org/10.1145/1998196.1998250.
  17. Marek Filakovský, Uli Wagner, and Stephan Zhechev. Embeddability of simplicial complexes is undecidable. In Proc. ACM-SIAM Symp. Discrete Algorithms (SODA), pages 767-785, 2020. URL: https://doi.org/10.1137/1.9781611975994.47.
  18. Emden R. Gansner, Yifan Hu, and Stephen G. Kobourov. On touching triangle graphs. In Ulrik Brandes and Sabine Cornelsen, editors, Proc. Graph Drawing (GD'10), volume 6502 of LNCS, pages 250-261. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-18469-7.
  19. Daniel Gonçalves, Benjamin Lévêque, and Alexandre Pinlou. Homothetic triangle representations of planar graphs. J. Graph Alg. Appl., 23(4):745-753, 2019. URL: https://doi.org/10.7155/jgaa.00509.
  20. Petr Hliněný. Contact graphs of line segments are NP-complete. Discrete Math., 235(1):95-106, 2001. URL: https://doi.org/10.1016/S0012-365X(00)00263-6.
  21. Petr Hliněný and Jan Kratochvíl. Representing graphs by disks and balls (a survey of recognition-complexity results). Discrete Math., 229(1-3):101-124, 2001. URL: https://doi.org/10.1016/S0012-365X(00)00204-1.
  22. Seok-Hee Hong and Hiroshi Nagamochi. Extending steinitz’s theorem to upward star-shaped polyhedra and spherical polyhedra. Algorithmica, 61(4):1022-1076, 2011. URL: https://doi.org/10.1007/s00453-011-9570-x.
  23. Lutz Kettner. Designing a data structure for polyhedral surfaces. In Proc. 14th Annu. ACM Symp. Comput. Geom. (SoCG'98), pages 146-154, 1998. URL: https://doi.org/10.1145/276884.276901.
  24. Tamás Kővari, Vera T. Sós, and Pál Turán. On a problem of K. Zarankiewicz. Coll. Math., 3(1):50-57, 1954. URL: http://eudml.org/doc/210011.
  25. Linda Kleist and Benjamin Rahman. Unit contact representations of grid subgraphs with regular polytopes in 2D and 3D. In Christian Duncan and Antonios Symvonis, editors, Proc. Graph Drawing (GD'14), volume 8871 of LNCS, pages 137-148. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-45803-7_12.
  26. Stephen G. Kobourov, Debajyoti Mondal, and Rahnuma Islam Nishat. Touching triangle representations for 3-connected planar graphs. In Walter Didimo and Maurizio Patrignani, editors, Proc. Graph Drawing (GD'12), volume 7704 of LNCS, pages 199-210. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-36763-2_18.
  27. Paul Koebe. Kontaktprobleme der konformen Abbildung. Berichte über die Verhandlungen der Sächsischen Akad. der Wissen. zu Leipzig. Math.-Phys. Klasse, 88:141-164, 1936. Google Scholar
  28. Jiří Matoušek, Martin Tancer, and Uli Wagner. Hardness of embedding simplicial complexes in ℝ^d. J. Europ. Math. Soc., 13(2):259-295, 2011. URL: https://doi.org/10.4171/JEMS/252.
  29. P. McMullen, C. Schulz, and J.M. Wills. Polyhedral 2-manifolds in E³ with unusually large genus. Israel J. Math., 46:127-144, 1983. URL: https://doi.org/10.1007/BF02760627.
  30. Arnaud de Mesmay, Yo’av Rieck, Eric Sedgwick, and Martin Tancer. Embeddability in ℝ³ is NP-hard. J. ACM, 67(4):1-29, 2020. URL: https://doi.org/10.1145/3396593.
  31. Jürgen Richter-Gebert. Realization spaces of polytopes, volume 1643 of Lecture Notes in Mathematics. Springer, 1996. URL: https://doi.org/10.1007/BFb0093761.
  32. Oded Schramm. Combinatorically Prescribed Packings and Applications to Conformal and Quasiconformal Maps. PhD thesis, Princeton University, 2007. URL: http://arxiv.org/abs/0709.0710.
  33. Arkadiy Skopenkov. Extendability of simplicial maps is undecidable. ArXiv report, 2020. URL: http://arxiv.org/abs/2008.00492.
  34. Arkadiy Skopenkov. Invariants of graph drawings in the plane. Arnold Math. J., 6:21-55, 2020. URL: https://doi.org/10.1007/s40598-019-00128-5.
  35. Ernst Steinitz. Polyeder und Raumeinteilungen. In Encyclopädie der mathematischen Wissenschaften, volume 3-1-2 (Geometrie), chapter 12, pages 1-139. B. G. Teubner, Leipzig, 1922. Google Scholar
  36. Szilassi polyhedron. Wikipedia entry. Accessed 2019-10-08. URL: https://en.wikipedia.org/wiki/Szilassi_polyhedron.
  37. Heinrich Tietze. Über das Problem der Nachbargebiete im Raum. Monatshefte für Mathematik und Physik, 16(1):211-216, 1905. URL: https://doi.org/10.1007/BF01693778.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact