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.
| Original language | English |
|---|---|
| Title of host publication | 37th International Symposium on Computational Geometry, SoCG 2021 |
| Editors | Kevin Buchin, Eric Colin de Verdiere |
| Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| ISBN (Electronic) | 9783959771849 |
| DOIs | |
| Publication status | Published - 1 Jun 2021 |
| Event | 37th International Symposium on Computational Geometry, SoCG 2021 - Virtual, Buffalo, United States Duration: 7 Jun 2021 → 11 Jun 2021 |
Publication series
| Name | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 189 |
| ISSN (Print) | 1868-8969 |
Conference
| Conference | 37th International Symposium on Computational Geometry, SoCG 2021 |
|---|---|
| Country/Territory | United States |
| City | Virtual, Buffalo |
| Period | 7/06/21 → 11/06/21 |
Bibliographical note
Funding Information:Funding Research on the topic of this paper was initiated at the 2nd Workshop on Applied Geometric Algorithms in Vierhouten, NL, supported by the Dutch Research Council (NWO); 639.023.208. Ignaz Rutter: Partially supported by the German Science Foundation (DFG); Ru 1903/3-1. Bettina Speckmann: Partially supported by the Dutch Research Council (NWO); 639.023.208.
Publisher Copyright:
© Tim Ophelders, Ignaz Rutter, Bettina Speckmann, and Kevin Verbeek; licensed under Creative Commons License CC-BY 4.0 37th International Symposium on Computational Geometry (SoCG 2021).
Funding
Funding Research on the topic of this paper was initiated at the 2nd Workshop on Applied Geometric Algorithms in Vierhouten, NL, supported by the Dutch Research Council (NWO); 639.023.208. Ignaz Rutter: Partially supported by the German Science Foundation (DFG); Ru 1903/3-1. Bettina Speckmann: Partially supported by the Dutch Research Council (NWO); 639.023.208.
Keywords
- Graph drawing
- Partial drawing extension
- Simple polygon