{"id":"arxiv/2610.42033","url":"https://arxiv.org/abs/2610.42033","tags":["cs.DM","cs.CC","math.CO"],"score":0,"title":"Treedepth is NP-Hard on Planar Graphs of Maximum Degree 3","domain":"cs.DM","source":"arxiv","authors":["Kolja Kühn"],"reviews":0,"subject":"cs.DM","summary":"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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-30","reactions":{}}