License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2021.55
URN: urn:nbn:de:0030-drops-138540
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13854/
Ophelders, Tim ;
Rutter, Ignaz ;
Speckmann, Bettina ;
Verbeek, Kevin
Polygon-Universal Graphs
Abstract
We study a fundamental question from graph drawing: given a pair (G,C) of a graph G and a cycle C in G together with a simple polygon P, is there a straight-line drawing of G inside P which maps C to P? We say that such a drawing of (G,C) respects P. We fully characterize those instances (G,C) which are polygon-universal, that is, they have a drawing that respects P for any simple (not necessarily convex) polygon P. Specifically, we identify two necessary conditions for an instance to be polygon-universal. Both conditions are based purely on graph and cycle distances and are easy to check. We show that these two conditions are also sufficient. Furthermore, if an instance (G,C) is planar, that is, if there exists a planar drawing of G with C on the outer face, we show that the same conditions guarantee for every simple polygon P the existence of a planar drawing of (G,C) that respects P. If (G,C) is polygon-universal, then our proofs directly imply a linear-time algorithm to construct a drawing that respects a given polygon P.
BibTeX - Entry
@InProceedings{ophelders_et_al:LIPIcs.SoCG.2021.55,
author = {Ophelders, Tim and Rutter, Ignaz and Speckmann, Bettina and Verbeek, Kevin},
title = {{Polygon-Universal Graphs}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {55:1--55:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13854},
URN = {urn:nbn:de:0030-drops-138540},
doi = {10.4230/LIPIcs.SoCG.2021.55},
annote = {Keywords: Graph drawing, partial drawing extension, simple polygon}
}
Keywords: |
|
Graph drawing, partial drawing extension, simple polygon |
Collection: |
|
37th International Symposium on Computational Geometry (SoCG 2021) |
Issue Date: |
|
2021 |
Date of publication: |
|
02.06.2021 |