In a graph $G$, the geodesic treewidth is defined as the smallest $k$ for which there exists a partition $\mathcal{P}$ such that $G/\mathcal{P}$ has treewidth $k$. Based on this concept, row treewidth is defined as the smallest $k$ such that $G \subseteq H \boxtimes P$ for some graph $H$ of treewidth $k$ and a path $P$. An equivalent definition of row treewidth is that there exists a partition $\mathcal{P}$ into disjoint unions of geodesics aligned with respect to some layering such that $G/\mathcal{P}$ has treewidth $k$.
We differentiate the two notions by showing that bounded row treewidth does not imply bounded geodesic treewidth. We also present a polynomial-time algorithm to decide whether a graph of treewidth 2 has geodesic treewidth 1, known to be NP-hard for row treewidth [Biedl, Eppstein, Ueckerdt, 2025].
More generally, we provide an algorithm to decide whether a given graph has geodesic treewidth at most $d$, which is XP in treewidth, while no such algorithm exists for row treewidth unless P = NP [Biedl, Eppstein, Ueckerdt, 2025].
On the other hand, we show that computing geodesic treewidth is NP-hard and that every graph with geodesic treewidth 1 has bounded row treewidth. Furthermore, we improve the best-known lower bound on the geodesic treewidth of planar graphs to 5.
Blogger's Review: This paper clearly distinguishes between geodesic and row treewidth, emphasizing their importance in complexity theory. The polynomial-time algorithm presented offers fresh insights into the study of treewidth in graphs, making it a noteworthy contribution to the field.