LIPIcs.SoCG.2021.55.pdf
- Filesize: 0.93 MB
- 15 pages
Document
Polygon-Universal Graphs
Authors
Ignaz Rutter 
,
Bettina Speckmann ,
-
Part of:
Volume:
37th International Symposium on Computational Geometry (SoCG 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-06-02
File
Document Identifiers
Author Details
Acknowledgements
Ignaz Rutter would like to thank Michael Hoffmann and Vincent Kusters for discussions on conjectures related to this paper.
Cite AsGet BibTex
Tim Ophelders, Ignaz Rutter, Bettina Speckmann, and Kevin Verbeek. Polygon-Universal Graphs. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.55
https://doi.org/10.4230/LIPIcs.SoCG.2021.55
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.
Subject Classification
ACM Subject Classification
- Human-centered computing → Graph drawings
Keywords
- Graph drawing
- partial drawing extension
- simple polygon
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Vít Jelínek, Jan Kratochvíl, Maurizio Patrignani, and Ignaz Rutter. Testing planarity of partially embedded graphs. ACM Transactions on Algorithms, 11(4):32:1-32:42, 2015. URL: https://doi.org/10.1145/2629341.
-
Patrizio Angelini, Philipp Kindermann, Andre Löffler, Lena Schlipf, and Antonios Symvonis. One-bend drawings of outerplanar graphs inside simple polygons. In Abstr. 36th European Workshop on Computational Geometry, pages 70:1-70:6, 2020.
- John Canny. Some algebraic and geometric computations in PSPACE. In Proc. 20th Symposium on Theory of Computing, page 460–467, 1988. URL: https://doi.org/10.1145/62212.62257.
- Erin W. Chambers, David Eppstein, Michael T. Goodrich, and Maarten Löffler. Drawing graphs in the plane with a prescribed outer face and polynomial area. Journal of Graph Algorithms and Applications, 16(2):243-259, 2012. URL: https://doi.org/10.7155/jgaa.00257.
- Michael G. Dobbins, Linda Kleist, Tillmann Miltzow, and Paweł Rzążewski. ∀ ∃ ℝ-completeness and area-universality. In Proc. 44th International Workshop on Graph-Theoretic Concepts in Computer Science, LNCS 11159, pages 164-175, 2018. URL: https://doi.org/10.1007/978-3-030-00256-5_14.
- Christian A. Duncan, Michael T. Goodrich, and Stephen G. Kobourov. Planar drawings of higher-genus graphs. Journal of Graph Algorithms and Applications, 15(1):7-32, 2011. URL: https://doi.org/10.1007/978-3-642-11805-0_7.
- Seok-Hee Hong and Hiroshi Nagamochi. Convex drawings of graphs with non-convex boundary constraints. Discrete Applied Mathematics, 156(12):2368-2380, 2008. URL: https://doi.org/10.1016/j.dam.2007.10.012.
- Vít Jelínek, Jan Kratochvíl, and Ignaz Rutter. A Kuratowski-type theorem for planarity of partially embedded graphs. Computational Geometry, 46(4):466-492, 2013. URL: https://doi.org/10.1016/j.comgeo.2012.07.005.
- Anna Lubiw, Tillmann Miltzow, and Debajyoti Mondal. The complexity of drawing a graph in a polygonal region. In Proc. 26th International Symposium on Graph Drawing and Network Visualization, LNCS 11282, pages 387-401, 2018. URL: https://doi.org/10.1007/978-3-030-04414-5_28.
- Tamara Mchedlidze, Martin Nöllenburg, and Ignaz Rutter. Extending convex partial drawings of graphs. Algorithmica, 76(1):47-67, 2016. URL: https://doi.org/10.1007/s00453-015-0018-6.
- Tamara Mchedlidze and Jérôme Urhausen. β-stars or on extending a drawing of a connected subgraph. In Proc. 26th International Symposium on Graph Drawing and Network Visualization, LNCS 11282, pages 416-429, 2018. URL: https://doi.org/10.1007/978-3-030-04414-5_30.
- Marcus Schaefer and Daniel Štefankovič. Fixed points, nash equilibria, and the existential theory of the reals. Theory of Computing Systems, 60:172-193, 2017. URL: https://doi.org/10.1007/s00224-015-9662-0.
- William T. Tutte. How to draw a graph. Proceedings of the London Mathematical Society, 13(3):743-768, 1963. URL: https://doi.org/10.1112/plms/s3-13.1.743.