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 K₅ as a subgraph does not admit a representation with convex polygons. On the other hand, K_4,4 admits such a representation, and so does every K_n where every edge is subdivided by a vertex. We also construct an infinite family (G_n) of graphs where G_n 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 }