Document Open Access Logo

Extending Partial Representations of Circle Graphs in Near-Linear Time

Authors Guido Brückner, Ignaz Rutter , Peter Stumpf

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.25.pdf
  • Filesize: 1.06 MB
  • 14 pages

Document Identifiers

Author Details

Guido Brückner
  • Karlsruhe Institute of Technology, Germany
Ignaz Rutter
  • University of Passau, Germany
Peter Stumpf
  • University of Passau, Germany

Funding

Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - Ru 1903/3-1.

Cite As Get BibTex

Guido Brückner, Ignaz Rutter, and Peter Stumpf. Extending Partial Representations of Circle Graphs in Near-Linear Time. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.MFCS.2022.25

Abstract

The partial representation extension problem generalizes the recognition problem for geometric intersection graphs. The input consists of a graph G, a subgraph H ⊆ G and a representation H of H. The question is whether G admits a representation G whose restriction to H is H. We study this question for circle graphs, which are intersection graphs of chords of a circle. Their representations are called chord diagrams.
We show that for a graph with n vertices and m edges the partial representation extension problem can be solved in O((n + m) α(n + m)) time, where α is the inverse Ackermann function. This improves over an O(n³)-time algorithm by Chaplick, Fulek and Klavík [2019]. The main technical contributions are a canonical way of orienting chord diagrams and a novel compact representation of the set of all canonically oriented chord diagrams that represent a given circle graph G, which is of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • circle graphs
  • partial representation extension
  • split decomposition tree
  • recognition algorithm

Metrics

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

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 Trans. Algorithms, 11(4):32:1-32:42, 2015. URL: https://doi.org/10.1145/2629341.
  2. Alan Arroyo, Martin Derka, and Irene Parada. Extending simple drawings. In Daniel Archambault and Csaba D. Tóth, editors, Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD'19), volume 11904 of Lecture Notes in Computer Science, pages 230-243. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-35802-0_18.
  3. André Bouchet. Reducing prime graphs and recognizing circle graphs. Combinatorica, 7(3):243-254, 1987. Google Scholar
  4. Steven Chaplick, Radoslav Fulek, and Pavel Klavík. Extending partial representations of circle graphs. J. Graph Theory, 91(4):365-394, 2019. Google Scholar
  5. Bruno Courcelle. Circle graphs and monadic second-order logic. Journal of Applied Logic, 6(3):416-442, September 2008. URL: https://doi.org/10.1016/j.jal.2007.05.001.
  6. William H. Cunningham. Decomposition of directed graphs. SIAM Journal on Algebraic Discrete Methods, 3(2):214-228, June 1982. URL: https://doi.org/10.1137/0603021.
  7. William H Cunningham and Jack Edmonds. A combinatorial decomposition theory. Canadian Journal of Mathematics, 32(3):734-765, 1980. Google Scholar
  8. Giuseppe Di Battista and Roberto Tamassia. On-line graph algorithms with SPQR-trees. In M.S. Paterson, editor, Proceedings of the 17th International Colloquium on Automata, Languages, and Programming, volume 443 of Lecture Notes in Computer Science, pages 598-611. Springer, 1990. Google Scholar
  9. 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.
  10. Csaba P Gabor, Kenneth J Supowit, and Wen-Lian Hsu. Recognizing circle graphs in polynomial time. Journal of the ACM (JACM), 36(3):435-473, 1989. Google Scholar
  11. Tibor Gallai. Transitiv orientierbare Graphen. Acta Mathematica Academiae Scientiarum Hungarica, 18:25-66, 1967. Google Scholar
  12. Emeric Gioan and Christophe Paul. Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs. Discrete Applied Mathematics, 160(6):708-733, 2012. Google Scholar
  13. Emeric Gioan, Christophe Paul, Marc Tedder, and Derek Corneil. Practical and efficient circle graph recognition. Algorithmica, 69(4):759-788, August 2014. URL: https://doi.org/10.1007/s00453-013-9745-8.
  14. Emeric Gioan, Christophe Paul, Mark Tedder, and Derek Corneil. Practical and efficient split decomposition via graph-labelled trees. Algorithmica, 69(4):789-843, 2014. URL: https://doi.org/10.1007/s00453-013-9752-9.
  15. Wen Lian Hsu. o(m⋅ n) algorithms for the recognition and isomorphism problems on circular-arc graphs. SIAM Journal on Computing, 24(3):411-439, 1995. URL: https://doi.org/10.1137/S0097539793260726.
  16. Vít Kalisz, Pavel Klavík, and Peter Zeman. Circle graph isomorphism in almost linear time. CoRR, abs/1908.09151, 2019. URL: http://arxiv.org/abs/1908.09151.
  17. 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, Proceedings of the 20th Annual European Symposium on Algorithms (ESA'12), volume 7501 of Lecture Notes in Computer Science, pages 671-682. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-33090-2_58.
  18. 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. In Algorithm Theory-SWAT 2014, pages 253-264. Springer, 2014. Google Scholar
  19. 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
  20. Pavel Klavík, Jan Kratochvíl, and Tomáš Vyskočil. Extending partial representations of interval graphs. In Mitsunori Ogihara and Jun Tarui, editors, Theory and Applications of Models of Computation: 8th Annual Conference, TAMC 2011, Tokyo. Proceedings, pages 276-285. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-20877-5_28.
  21. Tomasz Krawczyk and Bartosz Walczak. Extending partial representations of trapezoid graphs. In Hans L. Bodlaender and Gerhard J. Woeginger, editors, Proceedings of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, volume 10520 of Lecture Notes in Computer Science, pages 358-371. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-68705-6_27.
  22. Saunders Mac Lane. A structural characterization of planar combinatorial graphs. Duke Mathematical Journal, 3(3):460-472, 1937. Google Scholar
  23. Maurizio Patrignani. On extending a partial straight-line drawing. Int. J. Found. Comput. Sci., 17(5):1061-1070, 2006. URL: https://doi.org/10.1142/S0129054106004261.
  24. Jeremy Spinrad. Recognition of circle graphs. Journal of Algorithms, 16(2):264-282, 1994. 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 About DROPS Imprint Privacy Contact