Beyond outerplanarity

DOI10.1007/978-3-319-73915-1_42MaRDI QIDQ4625142zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(13)

• Quasi-planar Graphs
• Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
• Edge-minimum saturated \(k\)-planar drawings
• 2-Layer k-Planar Graphs
• Beyond planar graphs: introduction
• On fan-crossing and fan-crossing free graphs
• Cops and robbers on 1-planar 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)