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
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
