On outer k-planar graphs with a given drawing, most XALP-hard treewidth problems become FPT in k, while Binary CSP and Scattered Set remain XALP-complete, and outer k-planarity is placed in the parameter hierarchy.
On a tree-based variant of bandwidth and forbidding simple topological minors
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We obtain structure theorems for graphs excluding a fan (a path with a universal vertex) or a dipole ($K_{2,k}$) as a topological minor. The corresponding decompositions can be computed in FPT linear time. This is motivated by the study of a graph parameter we call treebandwidth which extends the graph parameter bandwidth by replacing the linear layout by a rooted tree such that neighbours in the graph are in ancestor-descendant relation in the tree. We deduce an approximation algorithm for treebandwidth running in FPT linear time from our structure theorems. We complement this result with a precise characterisation of the parameterised complexity of computing the parameter exactly.
fields
cs.DS 1years
2026 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
The Parameterized Complexity of Problems on Outer k-Planar Graphs
On outer k-planar graphs with a given drawing, most XALP-hard treewidth problems become FPT in k, while Binary CSP and Scattered Set remain XALP-complete, and outer k-planarity is placed in the parameter hierarchy.