Canonical tree-decompositions of finite graphs I. Existence and algorithms

Johannes Carmesin, Reinhard Diestel, Matthias Hamann, Fabian Hundertmark

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)
182 Downloads (Pure)


We construct tree-decompositions of graphs that distinguish all their k-blocks and tangles of order k, for any fixed integer k. We describe a family of algorithms to construct such decompositions, seeking to maximize their diversity subject to the requirement that they commute with graph isomorphisms. In particular, all the decompositions constructed are invariant under the automorphisms of the graph.
Original languageEnglish
Pages (from-to)1-24
JournalJournal of Combinatorial Theory. Series B
Early online date28 Aug 2015
Publication statusPublished - Jan 2016

Bibliographical note

23 pages, 5 figures


  • math.CO
  • graph
  • connectivity
  • tree-decomposition
  • k-block
  • tangle
  • profile
  • Tutte-decomposition


Dive into the research topics of 'Canonical tree-decompositions of finite graphs I. Existence and algorithms'. Together they form a unique fingerprint.

Cite this