Beyond Outerplanarity

Chaplick, Steven and Kryven, Myroslav and Liotta, Giuseppe and Löffler, Andre and Wolff, Alexander (2017) Beyond Outerplanarity. In: Graph Drawing and Network Visualization. GD 2017, September 25-27 , pp. 546-558(Official URL: https://doi.org/10.1007/978-3-319-73915-1_42).

Full text not available from this repository.

Abstract

We study straight-line drawings of graphs where the vertices are placed in convex position in the plane, i.e., convex drawings. We consider two families of graph classes with nice convex drawings: outer k-planar graphs, where each edge is crossed by at most k other edges; and, outer k-quasi-planar graphs where no k edges can mutually cross. We show that the outer k-planar graphs are (⌊4k+1‾‾‾‾‾‾√⌋+1) -degenerate, and consequently that every outer k-planar graph can be (⌊4k+1‾‾‾‾‾‾√⌋+2)-colored, and this bound is tight. We further show that every outer k-planar graph has a balanced separator of size at most 2k+3 . For each fixed k, these small balanced separators allow us to test outer k-planarity in quasi-polynomial time, i.e., none of these recognition problems are NP-hard unless ETH fails. For the outer k-quasi-planar graphs we discuss the edge-maximal graphs which have been considered previously under different names. We also construct planar 3-trees that are not outer 3-quasi-planar. Finally, we restrict outer k-planar and outer k-quasi-planar drawings to closed drawings, where the vertex sequence on the boundary is a cycle in the graph. For each k, we express closed outer k-planarity and closed outer k-quasi-planarity in extended monadic second-order logic. Thus, since outer k-planar graphs have bounded treewidth, closed outer k-planarity is linear-time testable by Courcelle’s Theorem.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.420 Crossings
P Styles > P.720 Straight-line
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1630

Actions (login required)

View Item View Item