2026-07-22T21:25:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9642 2024-03-06T10:44:36Z ddc:004 open_access

Treewidth-Two Graphs as a Free Algebra Doczkal, Christian Pous, Damien Treewidth Universal Algebra Rewriting 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christian Doczkal and Damien Pous 2018 Is Part Of LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2018.60 urn:nbn:de:0030-drops-96429 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.60 eng https://creativecommons.org/licenses/by/3.0/legalcode