Document Open Access Logo

Quasi-4-Connected Components

Author Martin Grohe

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.8.pdf
  • Filesize: 0.5 MB
  • 13 pages

Document Identifiers

Author Details

Martin Grohe

Cite As Get BibTex

Martin Grohe. Quasi-4-Connected Components. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.8

Abstract

We introduce a new decomposition of a graphs into quasi-4-connected components, where we call a graph quasi-4-connected if it is 3-connected and it only has separations of order 3 that separate a single vertex from the rest of the graph. Moreover, we give a cubic time algorithm computing the decomposition of a given graph.

Our decomposition into quasi-4-connected components refines the well-known decompositions of graphs into biconnected and triconnected components. We relate our decomposition to Robertson and Seymour's theory of tangles by establishing a correspondence between the quasi-4-connected components of a graph and its tangles of order 4.

Subject Classification

Keywords
  • decompositions
  • connectivity
  • tangles

Metrics

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

References

  1. J. Carmesin, R. Diestel, M. Hamann, and F. Hundertmark. Canonical tree-decompositions of finite graphs I. Existence and algorithms. ArXiv, arXiv:1305.4668v3 [math.CO], 2013. Google Scholar
  2. J. Carmesin, R. Diestel, M. Hamann, and F. Hundertmark. Canonical tree-decompositions of finite graphs II. Essential parts. ArXiv, arXiv:1305.4909v2 [math.CO], 2013. Google Scholar
  3. J. Carmesin, R. Diestel, F. Hundertmark, and M. Stein. Connectivity and tree structure in finite graphs. Combinatorica, 34(1):11-46, 2014. Google Scholar
  4. R. Diestel. Graph Theory. Springer-Verlag, 3rd edition, 2005. Google Scholar
  5. M. Grohe. Descriptive complexity, canonisation, and definable graph structure theory. Manuscript available at URL: http://www.lii.rwth-aachen.de/de/mitarbeiter/13-mitarbeiter/professoren/39-book-descriptive-complexity.html.
  6. M. Grohe. Fixed-point definability and polynomial time on graphs with excluded minors. Journal of the ACM, 59(5), 2012. Google Scholar
  7. M. Grohe. Quasi-4-connected components. ArXiv, arXiv:1602.04505 [cs.DM], 2016. Full version of this paper. Google Scholar
  8. M. Grohe. Tangles and connectivity in graphs. In A.-H. Dediu, J. Janoušek, C. Martín-Vide, and Bianca Truthe, editors, Proceedings of the 10th International Conference on Language and Automata Theory and Applications, volume 9618 of Lecture Notes in Computer Science, pages 24-41. Springer Verlag, 2016. Google Scholar
  9. M. Grohe and P. Schweitzer. Computing with tangles. In Proceedings of the 47th ACM Symposium on Theory of Computing, pages 683-692, 2015. Google Scholar
  10. J. E. Hopcroft and R. Tarjan. Dividing a graph into triconnected components. SIAM Journal on Computing, 2(2):135-158, 1973. Google Scholar
  11. F. Hundertmark. Profiles. An algebraic approach to combinatorial connectivity. ArXiv, arXiv:1110.6207v1 [math.CO], 2011. Google Scholar
  12. S. MacLane. A structural characterization of planar combinatorial graphs. Duke Mathematical Journal, 3(3):460-472, 1937. Google Scholar
  13. S. Makino. An algorithm for finding all the k-components of a digraph. International Journal of Computer Mathematics, 24(3-4):213-221, 1988. Google Scholar
  14. H. Nagamochi and T. Ibaraki. Algorithmic aspects of graph connectivity. Cambridge University Press, 2008. Google Scholar
  15. H. Nagamochi and T. Watanabe. Computing k-edge-connected components of a multigraph. EICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, E76-A(4):513-517, 1993. Google Scholar
  16. N. Robertson and P.D. Seymour. Graph minors I-XXIII. Journal of Combinatorial Theory, Series B 1982-2012. Google Scholar
  17. N. Robertson and P.D. Seymour. Graph minors X. Obstructions to tree-decomposition. Journal of Combinatorial Theory, Series B, 52:153-190, 1991. Google Scholar
  18. N. Robertson and P.D. Seymour. Graph minors XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B, 63:65-110, 1995. Google Scholar
  19. N. Robertson and P.D. Seymour. Graph minors XVI. Excluding a non-planar graph. Journal of Combinatorial Theory, Series B, 77:1-27, 1999. Google Scholar
  20. R. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146-160, 1972. Google Scholar
  21. W.T. Tutte. Graph Theory. Addison-Wesley, 1984. 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