H. Bodlaender

The Parameterized Complexity of Problems on Outer k-Planar Graphs

It is shown that outer k-planar graphs have mim-width at most k+2, that graphs of cut-width at most k are outer 2k-planar, and that graphs of feedback edge set number at most k are outer 6k-planar, and that many graph parameters are incomparable with outer k-planarity, thereby clarifying its position within the graph parameter hierarchy.