Outer 1-planar graphs
DOI10.1007/S00453-015-0002-1zbMATH Open1339.68197OpenAlexW2093843500MaRDI QIDQ289919FDOQ289919
Authors: Christopher Auer, Christian Bachmaier, Andreas Gleißner, Kathrin Hanauer, Daniel Neuwirth, Josef Reislhuber, Franz J. 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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)
Cites Work
- Title not available (Why is that?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Planarity and duality of finite and infinite graphs
- Every planar map is four colorable. I: Discharging
- Every planar map is four colorable. II: Reducibility
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Graphs drawn with few crossings per edge
- Ein Sechsfarbenproblem auf der Kugel
- Title not available (Why is that?)
- How to draw a planar graph on a grid
- The structure of 1-planar graphs
- Small area drawings of outerplanar graphs
- The book thickness of a graph
- Linear algorithms to recognize outerplanar and maximal outerplanar graphs
- Bemerkungen zu einem Sechsfarbenproblem von G. Ringel
- Density of straight-line 1-planar graph drawings
- Right angle crossing graphs and 1-planarity
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Depth-First Search and Kuratowski Subgraphs
- Rectilinear drawings of graphs
- A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
- Kuratowski's theorem
- Laying Out Graphs Using Queues
- Title not available (Why is that?)
- Straight-line drawings of outerplanar graphs in \(O(dn \log n)\) area
- 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
- Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs
Cited In (41)
- On book crossing numbers of the complete graph
- Title not available (Why is that?)
- Fan-crossing free graphs and their relationship to other beyond-planar graphs
- 1-Planar Graphs
- Incidence coloring of outer-1-planar graphs
- Orthogonal and smooth orthogonal layouts of 1-planar graphs with low edge complexity
- Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time
- Recognizing IC-planar and NIC-planar graphs
- The matching extendability of optimal 1-planar graphs
- Recognizing optimal 1-planar graphs in linear time
- Light paths and edges in families of outer-1-planar graphs
- 2-Layer k-Planar Graphs
- Beyond planar graphs: introduction
- Algorithms for 1-Planar Graphs
- Linear arboricity of outer-1-planar graphs
- Cops and robbers on 1-planar graphs
- On fan-crossing and fan-crossing free graphs
- Gap-Planar Graphs
- Optimal-area visibility representations of outer-1-plane graphs
- Total coloring of outer-1-planar graphs: the cold case
- Beyond outerplanarity
- Gap-planar graphs
- Drawing outer-1-planar graphs revisited
- Drawing outer-1-planar graphs revisited
- Correction to: ``Outer 1-planar graphs
- Recognizing outer 1-planar graphs in linear time
- \(\mathsf{NIC}\)-planar graphs
- Remarks on the joins of 1-planar graphs
- Strong Edge Coloring of Outerplane Graphs with Independent Crossings
- Total coloring of outer-1-planar graphs with near-independent crossings
- An annotated bibliography on 1-planarity
- Nonplanar Graph Drawings with k Vertices per Face
- \(k\)-planar graphs
- On list \(r\)-hued coloring of outer-1-planar graphs
- Recognizing and embedding simple optimal 2-planar graphs
- Characterizing and recognizing 4-map graphs
- Beyond-planarity: Turán-type results for non-planar bipartite graphs
- The family of fan-planar graphs
- 1-planarity testing and embedding: an experimental study
- On Aligned Bar 1-Visibility Graphs
- 1-fan-bundle-planar drawings of graphs
This page was built for publication: Outer 1-planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q289919)