Beyond outerplanarity

DOI10.1007/978-3-319-73915-1_42zbMATH Open1503.68213arXiv1708.08723OpenAlexW3037131127MaRDI QIDQ4625142FDOQ4625142

Authors: Steven Chaplick, Myroslav Kryven, Giuseppe Liotta, Andre Löffler, Alexander Wolff 

Publication date: 20 February 2019

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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 $(lfloorsqrt4k+1floor+1)$-degenerate, and consequently that every outer $k$-planar graph can be $(lfloorsqrt4k+1floor+2)$-colored, and this bound is tight. We further show that every outer $k$-planar graph has a balanced separator of size $O(k)$. This implies that every outer $k$-planar graph has treewidth $O(k)$. For fixed $k$, these small balanced separators allow us to obtain a simple quasi-polynomial time algorithm to test whether a given graph is outer $k$-planar, i.e., none of these recognition problems are NP-complete unless ETH fails. For the outer $k$-quasi-planar graphs we prove that, unlike other beyond-planar graph classes, every edge-maximal $n$-vertex outer $k$-quasi planar graph has the same number of edges, namely $$. 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 emph{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 emph{closed outer $k$-quasi-planarity} in extended monadic second-order logic. Thus, closed outer $k$-planarity is linear-time testable by Courcelle's Theorem.

Full work available at URL: https://arxiv.org/abs/1708.08723

Recommendations

• On triangulating \(k\)-outerplanar graphs
• A linear-time algorithm for testing full outer-2-planarity
• On the relationship between \(k\)-planar and \(k\)-quasi-planar graphs
• Outer 1-planar graphs
• Testing Full Outer-2-planarity in Linear Time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Graph structure and monadic second-order logic. A language-theoretic approach
• k-Degenerate Graphs
• On the complexity of \(k\)-SAT
• Graphs drawn with few crossings per edge
• Ein Sechsfarbenproblem auf der Kugel
• The graph crossing number and its variants: a survey
• Outer 1-planar graphs
• Title not available (Why is that?)
• The number of edges in \(k\)-quasi-planar graphs
• On the maximum number of edges in quasi-planar graphs
• Embedding planar graphs in four pages
• Graph minors. III. Planar tree-width
• A linear-time algorithm for testing outer-1-planarity
• A Turán-type theorem on chords of a convex polygon
• A generalization of diagonal flips in a convex polygon
• Convex geometric \((k+2)\)-quasiplanar representations of semi-bar \(k\)-visibility graphs
• On the maximum number of edges in topological graphs with no four pairwise crossing edges
• On line arrangements in the hyperbolic plane
• Applications of the crossing number
• Planar decompositions and the crossing number of graphs with an excluded minor
• An annotated bibliography on 1-planarity
• Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
• Structure of graphs with locally restricted crossings
• Treewidth of graphs with balanced separations
• 1-page and 2-page drawings with bounded number of crossings per edge
• On the relationship between \(k\)-planar and \(k\)-quasi-planar graphs
• Testing Full Outer-2-planarity in Linear Time
• Every property of outerplanar graphs is testable

Cited In (13)

• Quasi-planar Graphs
• Edge-minimum saturated \(k\)-planar drawings
• Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
• 2-Layer k-Planar Graphs
• Beyond planar graphs: introduction
• Cops and robbers on 1-planar graphs
• On fan-crossing and fan-crossing free graphs
• Bundled crossings revisited
• Parameterized analysis and crossing minimization problems
• \(k\)-planar graphs
• Beyond the standard IAU framework
• Structure and properties of locally outerplanar graphs
• Bundled crossings revisited

This page was built for publication: Beyond outerplanarity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4625142)