Treewidth-Two Graphs as a Free Algebra

Christian Doczkal (1) , Damien Pous (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

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.

Mots clés: Treewidth; Graph theory; Universal algebra; Rewriting

Domaines: Logique en informatique [cs.LO]

Christian Doczkal, Damien Pous. Treewidth-Two Graphs as a Free Algebra. 2018. ⟨hal-01780844v1⟩