Partitioning a Planar Graph into two Triangle-Forests

2024/01/27 by Kolja Knauer, Knauer, Kolja, Rambaud, Clément +1
Computer Science · Engineering · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Optimization and Packing Problems

paper · pdf · doi:10.48550/arxiv.2401.15394

Abstract

We show that the vertices of every planar graph can be partitioned into two sets, each inducing a so-called triangle-forest, i.e., a graph with no cycles of length more than three. We further discuss extensions to locally planar graphs. After finishing the paper we noticed that our main result was already proved much earlier by Carsten Thomassen [Decomposing a Planar Graph into Degenerate Graphs, JCTB 1995].

Related

• Partitioning triangle-free planar graphs into a forest and a linear forest
• Partitioning planar graphs without 4-cycles and 6-cycles into a forest and a disjoint union of paths
• Decomposing a triangle-free planar graph into a forest and a subcubic forest
• Partitioning a triangle-free planar graph into a forest and a forest of\n bounded degree
• (I,F)-partition of planar graphs without cycles of length 4, 6, or 9