Document Open Access Logo

Partial and Simultaneous Transitive Orientations via Modular Decompositions

Authors Miriam Münch , Ignaz Rutter , Peter Stumpf

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.51.pdf
  • Filesize: 0.95 MB
  • 16 pages

Document Identifiers

Author Details

Miriam Münch
  • Faculty of Computer Science and Mathematics, Universität Passau, Germany
Ignaz Rutter
  • Faculty of Computer Science and Mathematics, Universität Passau, Germany
Peter Stumpf
  • Faculty of Computer Science and Mathematics, Universität Passau, Germany

Funding

Funded by grant RU1903/3-1 of the German Research Foundation (DFG).

Cite AsGet BibTex

Miriam Münch, Ignaz Rutter, and Peter Stumpf. Partial and Simultaneous Transitive Orientations via Modular Decompositions. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 51:1-51:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ISAAC.2022.51

Abstract

A natural generalization of the recognition problem for a geometric graph class is the problem of extending a representation of a subgraph to a representation of the whole graph. A related problem is to find representations for multiple input graphs that coincide on subgraphs shared by the input graphs. A common restriction is the sunflower case where the shared graph is the same for each pair of input graphs. These problems translate to the setting of comparability graphs where the representations correspond to transitive orientations of their edges. We use modular decompositions to improve the runtime for the orientation extension problem and the sunflower orientation problem to linear time. We apply these results to improve the runtime for the partial representation problem and the sunflower case of the simultaneous representation problem for permutation graphs to linear time. We also give the first efficient algorithms for these problems on circular permutation graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Mathematics of computing → Graph algorithms
Keywords
  • representation extension
  • simultaneous representation
  • comparability graph
  • permutation graph
  • circular permutation graph
  • modular decomposition

Metrics

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

Related Versions

References

  1. 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. Google Scholar
  2. Patrizio Angelini, Giordano Da Lozzo, and Daniel Neuwirth. On some NP-complete SEFE problems. In Sudebkumar Prasant Pal and Kunihiko Sadakane, editors, In Proceedings of the 8th International Workshop on Algorithms and Computation (WALCOM'14), volume 8344 of Lecture Notes in Computer Science, pages 200-212. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-04657-0_20.
  3. Bengt Aspvall, Michael F. Plass, and Robert E. Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Information Processing Letters, 8(3):121-123, 1979. Google Scholar
  4. Thomas Bläsius, Stephen G. Kobourov, and Ignaz Rutter. Simultaneous embedding of planar graphs. Computing Research Repository, abs/1204.5853, 2012. URL: http://arxiv.org/abs/1204.5853.
  5. Thomas Bläsius and Ignaz Rutter. Simultaneous PQ-ordering with applications to constrained embedding problems. ACM Transactions on Algorithms, 12(2):16:1-16:46, 2015. URL: https://doi.org/10.1145/2738054.
  6. Jan Bok and Nikola Jedličková. A note on simultaneous representation problem for interval and circular-arc graphs. Computing Research Repository, 2018. URL: http://arxiv.org/abs/1811.04062.
  7. Kellogg S. Booth. PQ-tree algorithms. PhD thesis, University of California, Berkeley, 1975. Google Scholar
  8. 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. Google Scholar
  9. Peter Brass, Eowyn Cenek, Cristian A. Duncan, Alon Efrat, Cesim Erten, Dan P. Ismailescu, Stephen G. Kobourov, Anna Lubiw, and Joseph S.B. Mitchell. On simultaneous planar graph embeddings. Computational Geometry, 36(2):117-130, 2007. URL: https://doi.org/10.1016/j.comgeo.2006.05.006.
  10. Steven Chaplick, Paul Dorbec, Jan Kratochvíl, Mickael Montassier, and Juraj Stacho. Contact representations of planar graphs: Extending a partial representation is hard. In Dieter Kratsch and Ioan Todinca, editors, 40th International Workshop on Graph-theoretic concepts in computer science (WG'14), volume 8747 of Lecture Notes in Computer Science, pages 139-151. Springer, 2014. Google Scholar
  11. Steven Chaplick, Radoslav Fulek, and Pavel Klavík. Extending partial representations of circle graphs. Journal of Graph Theory, 91(4):365-394, 2019. Google Scholar
  12. Steven Chaplick, Philipp Kindermann, Jonathan Klawitter, Ignaz Rutter, and Alexander Wolff. Extending partial representations of rectangular duals with given contact orientations. In Tiziana Calamoneri and Federico Corò, editors, Proceedings of the 12th International Conference on Algorithms and Complexity, (CIAC '21), volume 12701 of Lecture Notes in Computer Science, pages 340-353. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-75242-2_24.
  13. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT press, Cambridge, 2009. Google Scholar
  14. 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, Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP'20), volume 168 of LIPIcs, pages 43:1-43:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.43.
  15. Alejandro Estrella-Balderrama, Elisabeth Gassner, Michael Jünger, Merijam Percan, Marcus Schaefer, and Michael Schulz. Simultaneous geometric graph embeddings. In Seok-Hee Hong, Takao Nishizeki, and Wu Quan, editors, Proceedings of 15th International Symposium on Graph Drawing (GD '07), pages 280-290. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-77537-9_28.
  16. Tibor Gallai. Transitiv orientierbare graphen. Acta Mathematica Academiae Scientiarum Hungarica, 18(1-2):25-66, 1967. Google Scholar
  17. Elisabeth Gassner, Michael Jünger, Merijam Percan, Marcus Schaefer, and Michael Schulz. Simultaneous graph embeddings with fixed edges. In Fedor V. Fomin, editor, 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'06), pages 325-335. Springer, 2006. URL: https://doi.org/10.1007/11917496_29.
  18. Paul C Gilmore and Alan J Hoffman. A characterization of comparability graphs and of interval graphs. Canadian Journal of Mathematics, 16:539-548, 1964. Google Scholar
  19. Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. Elsevier, London, 2004. Google Scholar
  20. Bernhard Haeupler, Krishnam R. Jampani, and Anna Lubiw. Testing simultaneous planarity when the common graph is 2-connected. Journal of Graph Algorithms and Applications, 17(3):147-171, 2013. Google Scholar
  21. Dov Harel and Robert E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing, 13(2):338-355, 1984. Google Scholar
  22. Krishnam Raju Jampani and Anna Lubiw. Simultaneous interval graphs. In Otfried Cheong, Kyung-Yong Chwa, and Kunsoo Park, editors, Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC' 10), pages 206-217. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-17517-6_20.
  23. Krishnam Raju Jampani and Anna Lubiw. The simultaneous representation problem for chordal, comparability and permutation graphs. Journal of Graph Algorithms and Applications, 16(2):283-315, 2012. Google Scholar
  24. 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. Google Scholar
  25. Pavel Klavík, Jan Kratochvíl, Tomasz Krawczyk, and Bartosz Walczak. Extending partial representations of function graphs and permutation graphs. In Leah Epstein and Paolo Ferragina, editors, 20th Annual European Symposium on Algorithms (ESA'12), Lecture Notes in Computer Science, pages 671-682. Springer, 2012. Google Scholar
  26. Pavel Klavík, Jan Kratochvíl, Yota Otachi, Ignaz Rutter, Toshiki Saitoh, Maria Saumell, and Tomáš Vyskočil. Extending partial representations of proper and unit interval graphs. Algorithmica, 77(4):1071-1104, 2017. Google Scholar
  27. Pavel Klavík, Jan Kratochvíl, Yota Otachi, and Toshiki Saitoh. Extending partial representations of subclasses of chordal graphs. Theoretical Computer Science, 576:85-101, 2015. Google Scholar
  28. Pavel Klavík, Jan Kratochvíl, Yota Otachi, Toshiki Saitoh, and Tomáš Vyskočil. Extending partial representations of interval graphs. Algorithmica, 78(3):945-967, 2017. Google Scholar
  29. Tomasz Krawczyk and Bartosz Walczak. Extending partial representations of trapezoid graphs. In Hans L. Bodlaender and Gerhard J. Woeginger, editors, 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'17), pages 358-371. Springer, 2017. Google Scholar
  30. Ross M McConnell and Jeremy P Spinrad. Modular decomposition and transitive orientation. Discrete Mathematics, 201(1-3):189-241, 1999. Google Scholar
  31. Miriam Münch, Ignaz Rutter, and Peter Stumpf. Partial and simultaneous transitive orientations via modular decomposition, 2022. URL: https://doi.org/10.48550/ARXIV.2209.13175.
  32. Maurizio Patrignani. On extending a partial straight-line drawing. International Journal of Foundations of Computer Science, 17(5):1061-1070, 2006. Google Scholar
  33. Doron Rotem and Jorge Urrutia. Circular permutation graphs. Networks, 12(4):429-437, 1982. Google Scholar
  34. Ignaz Rutter, Darren Strash, Peter Stumpf, and Michael Vollmer. Simultaneous representation of proper and unit interval graphs. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms (ESA'19), volume 144, page 80. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  35. Marcus Schaefer. Toward a theory of planarity: Hanani-Tutte and planarity variants. In 20th International Symposium on Graph Drawing (GD '12), pages 162-173. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-36763-2_15.
  36. R Sritharan. A linear time algorithm to recognize circular permutation graphs. Networks: An International Journal, 27(3):171-174, 1996. 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