Synchronized Planarity with Applications to Constrained Planarity Problems

Authors Thomas Bläsius, Simon D. Fink , Ignaz Rutter



PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.19.pdf
  • Filesize: 0.91 MB
  • 14 pages

Document Identifiers

Author Details

Thomas Bläsius
  • Faculty of Informatics, Karlsruhe Institute of Technology (KIT), Germany
Simon D. Fink
  • Faculty of Informatics and Mathematics, Universität Passau, Germany
Ignaz Rutter
  • Faculty of Informatics and Mathematics, Universität Passau, Germany

Cite AsGet BibTex

Thomas Bläsius, Simon D. Fink, and Ignaz Rutter. Synchronized Planarity with Applications to Constrained Planarity Problems. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.19

Abstract

We introduce the problem Synchronized Planarity. Roughly speaking, its input is a loop-free multi-graph together with synchronization constraints that, e.g., match pairs of vertices of equal degree by providing a bijection between their edges. Synchronized Planarity then asks whether the graph admits a crossing-free embedding into the plane such that the orders of edges around synchronized vertices are consistent. We show, on the one hand, that Synchronized Planarity can be solved in quadratic time, and, on the other hand, that it serves as a powerful modeling language that lets us easily formulate several constrained planarity problems as instances of Synchronized Planarity. In particular, this lets us solve Clustered Planarity in quadratic time, where the most efficient previously known algorithm has an upper bound of O(n⁸).

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Graphs and surfaces
Keywords
  • Planarity Testing
  • Constrained Planarity
  • Cluster Planarity
  • Atomic Embeddability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Hugo A. Akitaya, Radoslav Fulek, and Csaba D. Tóth. Recognizing weak embeddings of graphs. ACM Transactions on Algorithms, 15(4):1-27, 2019. URL: https://doi.org/10.1145/3344549.
  2. Patrizio Angelini and Giordano Da Lozzo. SEFE = c-planarity? The Computer Journal, 59(12):1831-1838, 2016. URL: https://doi.org/10.1093/comjnl/bxw035.
  3. Patrizio Angelini and Giordano Da Lozzo. Clustered planarity with pipes. Algorithmica, 81(6):2484-2526, 2019. URL: https://doi.org/10.1007/s00453-018-00541-w.
  4. Giuseppe Di Battista and Roberto Tamassia. On-line maintenance of triconnected components with SPQR-trees. Algorithmica, 15(4):302-318, 1996. URL: https://doi.org/10.1007/bf01961541.
  5. Thomas Bläsius, Annette Karrer, and Ignaz Rutter. Simultaneous embedding: Edge orderings, relative positions, cutvertices. Algorithmica, 80(4):1214-1277, 2017. URL: https://doi.org/10.1007/s00453-017-0301-9.
  6. Thomas Bläsius and Ignaz Rutter. Simultaneous PQ-ordering with applications to constrained embedding problems. ACM Trans. Algorithms, 12(2):16:1-16:46, 2016. URL: https://doi.org/10.1145/2738054.
  7. Thomas Bläsius, Stephen G. Kobourov, and Ignaz Rutter. Simultaneous embedding of planar graphs. In Roberto Tamassia, editor, Handbook of Graph Drawing and Visualization, chapter 11, pages 349-381. CRC Press, Taylor & Francis Group, 2013. URL: http://arxiv.org/abs/1204.5853.
  8. Thomas Bläsius and Ignaz Rutter. A new perspective on clustered planarity as a combinatorial embedding problem. Theoretical Computer Science, 609:306-315, 2016. URL: https://doi.org/10.1016/j.tcs.2015.10.011.
  9. Kellogg S. Booth and George S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences, 13(3):335-379, 1976. URL: https://doi.org/10.1016/s0022-0000(76)80045-1.
  10. Johannes Carmesin. Embedding simply connected 2-complexes in 3-space - V. A refined Kuratowski-type characterisation. CoRR, 2017. URL: http://arxiv.org/abs/1709.04659v3.
  11. Pier Francesco Cortese, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, and Maurizio Pizzonia. C-planarity of c-connected clustered graphs. Journal of Graph Algorithms and Applications, 12(2):225-262, 2008. URL: https://doi.org/10.7155/jgaa.00165.
  12. Pier Francesco Cortese and Maurizio Patrignani. Clustered planarity = flat clustered planarity. In Therese C. Biedl and Andreas Kerren, editors, Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD'18), volume 11282 of LNCS, pages 23-38. Springer, 2018. URL: https://doi.org/10.1007/978-3-030-04414-5_2.
  13. Qing-Wen Feng, Robert F. Cohen, and Peter Eades. Planarity for clustered graphs. In Paul G. Spirakis, editor, Proceedings of the 3rd Annual European Symposium on Algorithms (ESA'95), volume 979 of LNCS, pages 213-226. Springer, 1995. URL: https://doi.org/10.1007/3-540-60313-1_145.
  14. Radoslav Fulek, Jan Kynčl, Igor Malinović, and Dömötör Pálvölgyi. Clustered planarity testing revisited. The Electronic Journal of Combinatorics, 22(4), 2015. URL: https://doi.org/10.37236/5002.
  15. Radoslav Fulek and Csaba D. Tóth. Atomic embeddability, clustered planarity, and thickenability. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'20), pages 2876-2895. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.175.
  16. Carsten Gutwenger, Michael Jünger, Sebastian Leipert, Petra Mutzel, Merijam Percan, and René Weiskircher. Advances in c-planarity testing of clustered graphs. In Stephen G. Kobourov and Michael T. Goodrich, editors, Proceedings of the 10th International Symposium on Graph Drawing (GD'02), volume 2528 of LNCS, pages 220-235. Springer, 2002. URL: https://doi.org/10.1007/3-540-36151-0_21.
  17. Carsten Gutwenger, Karsten Klein, and Petra Mutzel. Planarity testing and optimal edge insertion with embedding constraints. Journal of Graph Algorithms and Applications, 12(1):73-95, 2008. URL: https://doi.org/10.7155/jgaa.00160.
  18. Carsten Gutwenger and Petra Mutzel. A linear time implementation of SPQR-trees. In Joe Marks, editor, Proceedings of the 8th International Symposium on Graph Drawing (GD'00), volume 1984 of LNCS, pages 77-90. Springer, 2000. URL: https://doi.org/10.1007/3-540-44541-2_8.
  19. F. Hadlock. Finding a maximum cut of a planar graph in polynomial time. SIAM J. Comput., 4(3):221-225, 1975. URL: https://doi.org/10.1137/0204019.
  20. John E. Hopcroft and Robert Endre Tarjan. Dividing a graph into triconnected components. SIAM J. Comput., 2(3):135-158, 1973. URL: https://doi.org/10.1137/0202012.
  21. Wen-Lian Hsu. PC-trees vs. PQ-trees. In Jie Wang, editor, Proceedings of the 7th Annual International Conference on Computing and Combinatorics (COCOON'01), volume 2108 of LNCS, pages 207-217. Springer, 2001. URL: https://doi.org/10.1007/3-540-44679-6_23.
  22. Thomas Lengauer. Hierarchical planarity testing algorithms. Journal of the ACM, 36(3):474-509, 1989. URL: https://doi.org/10.1145/65950.65952.
  23. L. Neuwirth. An algorithm for the construction of 3-manifolds from 2-complexes. Mathematical Proceedings of the Cambridge Philosophical Society, 64(3):603-614, 1968. URL: https://doi.org/10.1017/S0305004100043279.
  24. Marcus Schaefer. Toward a theory of planarity: Hanani-tutte and planarity variants. Journal of Graph Algorithms and Applications, 17(4):367-440, 2013. URL: https://doi.org/10.7155/jgaa.00298.
  25. Wei-Kuan Shih and Wen-Lian Hsu. A new planarity test. Theoretical Computer Science, 223(1-2):179-191, 1999. URL: https://doi.org/10.1016/s0304-3975(98)00120-0.
  26. Roberto Tamassia, editor. Handbook of Graph Drawing and Visualization. CRC Press, Taylor & Francis Group, 2014. URL: https://doi.org/10.1201/b15385.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail