Document Open Access Logo

Parameterized Algorithms for Upward Planarity

Authors Steven Chaplick , Emilio Di Giacomo , Fabrizio Frati , Robert Ganian , Chrysanthi N. Raftopoulou , Kirill Simonov

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.26.pdf
  • Filesize: 1.23 MB
  • 16 pages

Document Identifiers

Author Details

Steven Chaplick
  • Maastricht University, The Netherlands
Emilio Di Giacomo
  • Università degli Studi di Perugia, Italy
Fabrizio Frati
  • Roma Tre University, Rome, Italy
Robert Ganian
  • Technische Universität Wien, Austria
Chrysanthi N. Raftopoulou
  • National Technical University of Athens, Greece
Kirill Simonov
  • Technische Universität Wien, Austria

Funding

  • Di Giacomo, Emilio: MIUR, grant 20174LF3T8, Dip. Ing. - UNIPG, grants RICBA19FM and RICBA20EDG.
  • Frati, Fabrizio: MIUR, grant 20174LF3T8.
  • Ganian, Robert: Austrian Science Fund (FWF) Project Y1329.
  • Raftopoulou, Chrysanthi N.: NTUA research program ΠEBE 2020.
  • Simonov, Kirill: Austrian Science Fund (FWF) Project P31336.

Acknowledgements

The authors thank Fabrizio Montecchiani and Giuseppe Liotta for fruitful discussions on the topic of upward planarity. This research was initiated at Dagstuhl Seminar 21293: Parameterized Complexity in Graph Drawing [Ganian et al., 2021].

Cite AsGet BibTex

Steven Chaplick, Emilio Di Giacomo, Fabrizio Frati, Robert Ganian, Chrysanthi N. Raftopoulou, and Kirill Simonov. Parameterized Algorithms for Upward Planarity. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 26:1-26:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SoCG.2022.26

Abstract

We obtain new parameterized algorithms for the classical problem of determining whether a directed acyclic graph admits an upward planar drawing. Our results include a new fixed-parameter algorithm parameterized by the number of sources, an XP-algorithm parameterized by treewidth, and a fixed-parameter algorithm parameterized by treedepth. All three algorithms are obtained using a novel framework for the problem that combines SPQR tree-decompositions with parameterized techniques. Our approach unifies and pushes beyond previous tractability results for the problem on series-parallel digraphs, single-source digraphs and outerplanar digraphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Human-centered computing → Graph drawings
Keywords
  • Upward planarity
  • parameterized algorithms
  • SPQR trees
  • treewidth
  • treedepth

Metrics

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

Related Versions

References

  1. Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Yota Otachi. Grundy distinguishes treewidth from pathwidth. In 28th Annual European Symposium on Algorithms, ESA 2020, volume 173 of LIPIcs, pages 14:1-14:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.14.
  2. Paola Bertolazzi, Giuseppe Di Battista, Carlo Mannino, and Roberto Tamassia. Optimal upward planarity testing of single-source digraphs. SIAM J. Comput., 27(1):132-169, 1998. Google Scholar
  3. Paola Bertolazzi, Giuseppe Di Battista, Giuseppe Liotta, and Carlo Mannino. Upward drawings of triconnected digraphs. Algorithmica, 12(6):476-497, 1994. Google Scholar
  4. Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, and Christian Wulff-Nilsen. Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time. SIAM J. Comput., 46(4):1280-1303, 2017. Google Scholar
  5. Guido Brückner, Markus Himmel, and Ignaz Rutter. An SPQR-tree-like embedding representation for upward planarity. In Daniel Archambault and Csaba D. Tóth, editors, 27th International Symposium on Graph Drawing and Network Visualization, GD 2019, volume 11904 of Lecture Notes in Computer Science, pages 517-531. Springer, 2019. Google Scholar
  6. Guido Brückner and Ignaz Rutter. Partial and constrained level planarity. In Philip N. Klein, editor, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 2000-2011. SIAM, 2017. Google Scholar
  7. Hubert Y. Chan. A parameterized algorithm for upward planarity testing. In Susanne Albers and Tomasz Radzik, editors, 12th Annual European Symposium on Algorithms, ESA 2004, volume 3221 of Lecture Notes in Computer Science, pages 157-168. Springer, 2004. Google Scholar
  8. Steven Chaplick, Emilio Di Giacomo, Fabrizio Frati, Robert Ganian, Chrysanthi N. Raftopoulou, and Kirill Simonov. Parameterized algorithms for upward planarity. CoRR, abs/2203.05364, 2022. URL: https://arxiv.org/abs/2203.05364.
  9. Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. Google Scholar
  10. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  11. Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, 1999. Google Scholar
  12. Giuseppe Di Battista and Roberto Tamassia. On-line planarity testing. SIAM J. Comput., 25(5):956-997, 1996. Google Scholar
  13. Walter Didimo, Francesco Giordano, and Giuseppe Liotta. Upward spirality and upward planarity testing. SIAM J. Discret. Math., 23(4):1842-1899, 2009. Google Scholar
  14. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  15. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  16. Eduard Eiben, Robert Ganian, Thekla Hamm, Fabian Klute, and Martin Nöllenburg. Extending partial 1-planar drawings. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, volume 168 of LIPIcs, pages 43:1-43:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  17. Robert Ganian, Thekla Hamm, Fabian Klute, Irene Parada, and Birgit Vogtenhuber. Crossing-optimal extension of simple drawings. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, volume 198 of LIPIcs, pages 72:1-72:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  18. Robert Ganian, Petr Hlinený, Joachim Kneis, Daniel Meister, Jan Obdrzálek, Peter Rossmanith, and Somnath Sikdar. Are there any good digraph width measures? J. Comb. Theory, Ser. B, 116:250-286, 2016. Google Scholar
  19. Robert Ganian, Fabrizio Montecchiani, Martin Nöllenburg, and Meirav Zehavi. Parameterized Complexity in Graph Drawing (Dagstuhl Seminar 21293). Dagstuhl Reports, 11(6):82-123, 2021. Google Scholar
  20. Ashim Garg and Roberto Tamassia. On the computational complexity of upward and rectilinear planarity testing. In Roberto Tamassia and Ioannis G. Tollis, editors, DIMACS International Workshop on Graph Drawing, GD '94, volume 894 of Lecture Notes in Computer Science, pages 286-297. Springer, 1994. Google Scholar
  21. Ashim Garg and Roberto Tamassia. On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput., 31(2):601-625, 2001. Google Scholar
  22. Carsten Gutwenger and Petra Mutzel. A linear time implementation of SPQR-trees. In Joe Marks, editor, 8th International Symposium on Graph Drawing, GD '00, volume 1984 of Lecture Notes in Computer Science, pages 77-90. Springer, 2000. Google Scholar
  23. Patrick Healy and Karol Lynch. Two fixed-parameter tractable algorithms for testing upward planarity. Int. J. Found. Comput. Sci., 17(5):1095-1114, 2006. URL: https://doi.org/10.1142/S0129054106004285.
  24. 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.
  25. Michael D. Hutton and Anna Lubiw. Upward planar drawing of single source acyclic digraphs. In Alok Aggarwal, editor, 2nd Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, SODA 1991, pages 203-211. ACM/SIAM, 1991. Google Scholar
  26. Michael D. Hutton and Anna Lubiw. Upward planar drawing of single-source acyclic digraphs. SIAM J. Comput., 25(2):291-311, 1996. URL: https://doi.org/10.1137/S0097539792235906.
  27. Jaroslav Nesetril and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-27875-4.
  28. Achilleas Papakostas. Upward planarity testing of outerplanar dags. In Roberto Tamassia and Ioannis G. Tollis, editors, DIMACS International Workshop on Graph Drawing, GD '94, volume 894 of Lecture Notes in Computer Science, pages 298-306. Springer, 1994. URL: https://doi.org/10.1007/3-540-58950-3_385.
  29. Neil Robertson and Paul D. Seymour. Graph minors. III. Planar tree-width. J. Comb. Theory, Ser. B, 36(1):49-64, 1984. Google Scholar
  30. William T. Trotter and John I. Moore Jr. The dimension of planar posets. J. Comb. Theory, Ser. B, 22(1):54-67, 1977. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact