Beyond OuterplanarityChaplick, 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 2527 , pp. 546558(Official URL: https://doi.org/10.1007/9783319739151_42). Full text not available from this repository.
Official URL: https://doi.org/10.1007/9783319739151_42
AbstractWe study straightline 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 kplanar graphs, where each edge is crossed by at most k other edges; and, outer kquasiplanar graphs where no k edges can mutually cross. We show that the outer kplanar graphs are (⌊4k+1‾‾‾‾‾‾√⌋+1) degenerate, and consequently that every outer kplanar graph can be (⌊4k+1‾‾‾‾‾‾√⌋+2)colored, and this bound is tight. We further show that every outer kplanar graph has a balanced separator of size at most 2k+3 . For each fixed k, these small balanced separators allow us to test outer kplanarity in quasipolynomial time, i.e., none of these recognition problems are NPhard unless ETH fails. For the outer kquasiplanar graphs we discuss the edgemaximal graphs which have been considered previously under different names. We also construct planar 3trees that are not outer 3quasiplanar. Finally, we restrict outer kplanar and outer kquasiplanar drawings to closed drawings, where the vertex sequence on the boundary is a cycle in the graph. For each k, we express closed outer kplanarity and closed outer kquasiplanarity in extended monadic secondorder logic. Thus, since outer kplanar graphs have bounded treewidth, closed outer kplanarity is lineartime testable by Courcelle’s Theorem.
Actions (login required)
