Treewidth-Two Graphs as a Free Algebra

Christian Doczkal 1, 2 Damien Pous 1, 2
1 PLUME - Preuves et Langages
LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We give a new and elementary proof that the graphs of treewidth at most two can be seen as a free algebra. This result was presented last year at MFCS and was proved through an elaborate analysis of the structure of K4-free graphs, ultimately reproving the well-known fact that the graphs of treewidth at most two are precisely those excluding K4 as a minor. Our new proof is based on a confluent and terminating rewriting system for treewidth-two graphs and does not involve graph minors anymore. The new strategy is simpler and robust in the sense that it can be adapted to subclasses of treewidth-two graphs. It could also be amenable to handle graphs of larger treewidth, where the excluded minors are typically unknown.
Document type :
Conference papers
Liste complète des métadonnées

https://hal.archives-ouvertes.fr/hal-01780844
Contributor : Damien Pous <>
Submitted on : Wednesday, September 12, 2018 - 1:30:11 PM
Last modification on : Tuesday, April 16, 2019 - 3:31:05 PM

File

tw2fa.pdf
Files produced by the author(s)

Identifiers

Citation

Christian Doczkal, Damien Pous. Treewidth-Two Graphs as a Free Algebra. Mathematical Foundations of Computer Science, Aug 2018, Liverpool, United Kingdom. ⟨10.4230/LIPIcs.MFCS.2018.60⟩. ⟨hal-01780844v3⟩

Share

Metrics

Record views

94

Files downloads

62