Outer 1-planar graphs
From MaRDI portal
Publication:289919
DOI10.1007/s00453-015-0002-1zbMath1339.68197OpenAlexW2093843500MaRDI QIDQ289919
Christopher Auer, Kathrin Hanauer, Daniel Neuwirth, Josef Reislhuber, Christian Bachmaier, Andreas Gleißner, Franz-Josef Brandenburg
Publication date: 31 May 2016
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-015-0002-1
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (32)
Recognizing and embedding simple optimal 2-planar graphs ⋮ Optimal-area visibility representations of outer-1-plane graphs ⋮ On fan-crossing and fan-crossing free graphs ⋮ Recognizing IC-Planar and NIC-Planar Graphs ⋮ Drawing outer-1-planar graphs revisited ⋮ Fan-crossing free graphs and their relationship to other beyond-planar graphs ⋮ An annotated bibliography on 1-planarity ⋮ Correction to: ``Outer 1-planar graphs ⋮ \(\mathsf{NIC}\)-planar graphs ⋮ Total coloring of outer-1-planar graphs with near-independent crossings ⋮ The family of fan-planar graphs ⋮ Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time ⋮ Recognizing optimal 1-planar graphs in linear time ⋮ 1-fan-bundle-planar drawings of graphs ⋮ Gap-Planar Graphs ⋮ Beyond Outerplanarity ⋮ Orthogonal and smooth orthogonal layouts of 1-planar graphs with low edge complexity ⋮ Characterizing and recognizing 4-map graphs ⋮ Light paths and edges in families of outer-1-planar graphs ⋮ The matching extendability of optimal 1-planar graphs ⋮ Unnamed Item ⋮ Gap-planar graphs ⋮ Linear arboricity of outer-1-planar graphs ⋮ Remarks on the joins of 1-planar graphs ⋮ On Aligned Bar 1-Visibility Graphs ⋮ Total coloring of outer-1-planar graphs: the cold case ⋮ Beyond Planar Graphs: Introduction ⋮ Algorithms for 1-Planar Graphs ⋮ $$\textit{\textbf{k}}$$-Planar Graphs ⋮ 1-planarity testing and embedding: an experimental study ⋮ 2-Layer k-Planar Graphs ⋮ On list \(r\)-hued coloring of outer-1-planar graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
- Straight-line drawings of outerplanar graphs in \(O(dn \log n)\) area
- Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs
- How to draw a planar graph on a grid
- The structure of 1-planar graphs
- Small area drawings of outerplanar graphs
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- The book thickness of a graph
- Planarity and duality of finite and infinite graphs
- Linear algorithms to recognize outerplanar and maximal outerplanar graphs
- Bemerkungen zu einem Sechsfarbenproblem von G. Ringel
- Every planar map is four colorable. I: Discharging
- Every planar map is four colorable. II: Reducibility
- Graphs drawn with few crossings per edge
- Density of straight-line 1-planar graph drawings
- Right angle crossing graphs and 1-planarity
- Ein Sechsfarbenproblem auf der Kugel
- Crossing number is hard for cubic graphs
- Parameterized Complexity of 1-Planarity
- A Linear-Time Algorithm for Testing Outer-1-Planarity
- Straight-Line Grid Drawings of 3-Connected 1-Planar Graphs
- Recognizing Outer 1-Planar Graphs in Linear Time
- Fáry’s Theorem for 1-Planar Graphs
- Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
- Depth-First Search and Kuratowski Subgraphs
- Rectilinear drawings of graphs
- Kuratowski's theorem
- Laying Out Graphs Using Queues
- On-Line Planarity Testing
- On the Density of Maximal 1-Planar Graphs
- 1-Planarity of Graphs with a Rotation System
- EVERY OUTER-1-PLANE GRAPH HAS A RIGHT ANGLE CROSSING DRAWING
- Layout of Graphs with Bounded Tree-Width
- Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
- On the Queue Number of Planar Graphs
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
This page was built for publication: Outer 1-planar graphs