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

@misc{kuhn2026treedepth,
  title = {{Treedepth is NP-Hard on Planar Graphs of Maximum Degree 3}},
  author = {Kolja Kühn},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.42033},
  eprint = {2610.42033},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.42033},
}

TY  - UNPB
TI  - Treedepth is NP-Hard on Planar Graphs of Maximum Degree 3
AU  - Kolja Kühn
PY  - 2026
DA  - 2026/10/30
PB  - arXiv
DO  - 10.48550/arxiv.2610.42033
UR  - https://arxiv.org/abs/2610.42033
AB  - 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 ≠ 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.
ER  -