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.
Bodlaender, Carla Groenland, and Hugo Jacob
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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.