Treewidth-Two Graphs as a Free Algebra

Christian Doczkal 1 Damien Pous 1
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.
Type de document :
Communication dans un congrès
Mathematical Foundations of Computer Science, Aug 2018, Liverpool, United Kingdom. 〈10.4230/LIPIcs.MFCS.2018.60〉
Liste complète des métadonnées

https://hal.archives-ouvertes.fr/hal-01780844
Contributeur : Damien Pous <>
Soumis le : mercredi 12 septembre 2018 - 13:30:11
Dernière modification le : lundi 22 octobre 2018 - 12:56:02

Fichier

tw2fa.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

54

Téléchargements de fichiers

20