Separating Geodesic Structure and Product Structure

Abstract

The geodesic treewidth of a graph $G$ is the smallest $k$ for which there is a partition $\mathcal{P}$ into geodesics such that $G/\mathcal{P}$ has treewidth $k$, where $G/\mathcal{P}$ is obtained from $G$ by contracting each part of $\mathcal{P}$. Based on this notion, row treewidth was developed and is defined for a graph $G$ as the smallest $k$ such that $G\subseteq H⊠P$ for some graph $H$ of treewidth $k$ and a path $P$. Equivalently, the row treewidth of a graph $G$ is the smallest $k$ for which there is a partition $\mathcal{P}$ into disjoint unions of geodesics that are aligned with respect to some layering such that $G/\mathcal{P}$ has treewidth $k$. We separate the two notions by showing that bounded row treewidth does not imply bounded geodesic treewidth and by presenting a polynomial-time algorithm to decide whether a graph of treewidth 2 has geodesic treewidth 1, which is 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$ that is XP in the treewidth, whereas there is no such algorithm for row treewidth, unless P = NP [Biedl, Eppstein, Ueckerdt, 2025]. On the other hand, we show that computing the geodesic treewidth is NP-hard and that every graph with geodesic treewidth 1 has bounded row treewidth. Moreover, we improve the best known lower bound on the geodesic treewidth of planar graphs to 5.

An extended abstract of this paper appears in the proceedings of the 34th Annual European Symposium on Algorithms (ESA 2026)