Paperlane

no. 6 · Monday 2 November 2026

Treedepth is NP-Hard on Planar Graphs of Maximum Degree 3

Kolja Kühn

math.CO · via cs.DM · 14 pp

Abstract

Treedepth is an important parameter in algorithmic graph theory. It is known that the problem of computing the treedepth of a graph is NP-hard. It has been an open problem whether treedepth can be computed in polynomial time when the input graph is restricted to be planar, or of bounded degree. Assuming $P \neq NP$, we answer both questions in the negative: Under polynomial-time Turing reductions, it is NP-hard to compute the treedepth of planar graphs with maximum degree 3. This degree bound is best possible, since treedepth can be computed efficiently on graphs of maximum degree 2.

comments
14 pages, 5 figures
fields
Combinatorics
pdf ↗ page arXiv:2610.42033 ↗