Veröffentlichung

Titel:
Representing Graphs by Polygons with Edge Contacts in 3D
AutorInnen:
Elena Arseneva
Linda Kleist
Boris Klemz
Maarten Löffler
André Schulz
Birgit Vogtenhuber
Alexander Wolff
Kategorie:
Workshopbeiträge
erschienen in:
Proceedings of the 36th European Workshop on Computational Geometry (EuroCG'20)
Abstract:

A graph has an edge-contact representation with polygons if its vertices can be represented by interior-disjoint polygons such that two polygons share a common edge if and only if the corresponding vertices are adjacent. In this work we study representations in 3D.
We show that every graph has an edge-contact representation with polygons in 3D, while this is not the case if we additionally require that the polygons are convex. In particular, we show that every graph containing K5 as a subgraph does not admit a representation with convex polygons. On the other hand, K4,4 admits such a representation, and so does every Kn where every edge is subdivided by a vertex. We also construct an infinite family (Gn) of graphs where Gn has n vertices, 6n - o(n) edges, and admits an edge-contact representation with convex polygons in 3D.

Download:
Universität Würzburg
BibTeX-Eintrag:
@inproceedings{akklsvw-rgpec-EuroCG20, added-at = {2021-08-30T00:23:27.000+0200}, author = {Arseneva, Elena and Kleist, Linda and Klemz, Boris and L{\"o}ffler, Maarten and Schulz, Andr{\'e} and Vogtenhuber, Birgit and Wolff, Alexander}, biburl = {https://www.bibsonomy.org/bibtex/266f2f8d2370b5fc4137def1f1938eb0d/awolff}, booktitle = {Proc. 36th European Workshop on Computational Geometry (EuroCG'20)}, editor = {Chaplick, Steven and Kindermann, Philipp and Wolff, Alexander}, interhash = {fa7ff6e5c70f0254f2b3b5fd25190209}, intrahash = {66f2f8d2370b5fc4137def1f1938eb0d}, keywords = {myown}, pages = {53:1--8}, pdf = {http://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/papers/eurocg20_paper_53.pdf}, timestamp = {2021-08-30T00:23:51.000+0200}, title = {Representing Graphs by Polygons with Edge Contacts in {3D}}, video = {https://youtu.be/0MGg7N6Z24E}, year = 2020 }
Christoph Doppelbauer | 21.10.2021