{"ID":5675344,"CreatedAt":"2026-07-03T01:40:09.565152011Z","UpdatedAt":"2026-07-07T01:06:03.009715918Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.02098","arxiv_id":"2607.02098","title":"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 \\boxtimes 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.","short_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...","url_abs":"https://arxiv.org/abs/2607.02098","url_pdf":"https://arxiv.org/pdf/2607.02098v1","authors":"[\"Laura Merker\",\"Lena Scherzer\",\"Samuel Schneider\"]","published":"2026-07-02T12:34:27Z","proceeding":"math.CO","tasks":"[\"math.CO\",\"cs.DM\",\"cs.DS\"]","methods":"[]","has_code":false}