Treewidth-Two Graphs as a Free Algebra

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 originally established through an elaborate analysis of the structure of K_4-free graphs, ultimately reproving the well-known fact that the graphs of treewidth at most two are precisely those excluding K_4 as a minor. Our new proof is based on a confluent and terminating rewriting system for term-labeled 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, e. g. , graphs without self-loops.

Authors

• Christian Doczkal
• Damien Pous

Keywords

• Treewidth
• Universal Algebra
• Rewriting