A new parameter family, k-treedepth, is characterized by excluded minors T□P_l for all k-vertex trees T, unifying treedepth, the ladder theorem, and the Grid-Minor Theorem.
Homotopy height, grid-major height and graph-drawing height
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
It is well-known that both the pathwidth and the outer-planarity of a graph can be used to obtain lower bounds on the height of a planar straight-line drawing of a graph. But both bounds fall short for some graphs. In this paper, we consider two other parameters, the (simple) homotopy height and the (simple) grid-major height. We discuss the relationship between them and to the other parameters, and argue that they give lower bounds on the straight-line drawing height that are never worse than the ones obtained from pathwidth and outer-planarity.
fields
math.CO 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Excluding a rectangular grid
A new parameter family, k-treedepth, is characterized by excluded minors T□P_l for all k-vertex trees T, unifying treedepth, the ladder theorem, and the Grid-Minor Theorem.