A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
From MaRDI portal
Publication:391976
DOI10.1016/j.tcs.2013.09.029zbMath1407.68354OpenAlexW2021281967WikidataQ62042415 ScholiaQ62042415MaRDI QIDQ391976
Pascal Schweitzer, Peter Eades, Naoki Katoh, Seok-Hee Hong, Yusuke Suzuki, Giuseppe Liotta
Publication date: 13 January 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2013.09.029
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (26)
The density of fan-planar graphs ⋮ Outer 1-planar graphs ⋮ Edge-minimum saturated \(k\)-planar drawings ⋮ Recognizing and embedding simple optimal 2-planar graphs ⋮ \(K_7\)-minors in optimal 1-planar graphs ⋮ On the recognition of fan-planar and maximal outer-fan-planar graphs ⋮ Maximal 1-plane graphs with dominating vertices ⋮ Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time ⋮ On the edge crossing properties of Euclidean minimum weight Laman graphs ⋮ Recognizing optimal 1-planar graphs in linear time ⋮ 1-fan-bundle-planar drawings of graphs ⋮ Gap-Planar Graphs ⋮ A linear-time algorithm for testing full outer-2-planarity ⋮ A linear-time algorithm for testing outer-1-planarity ⋮ Re-embedding a 1-plane graph for a straight-line drawing in linear time ⋮ On partitioning the edges of 1-plane graphs ⋮ Gap-planar graphs ⋮ Ortho-polygon visibility representations of embedded graphs ⋮ The maximal 1-planarity and crossing numbers of graphs ⋮ Generating polyhedral quadrangulations of the projective plane ⋮ Testing Full Outer-2-planarity in Linear Time ⋮ Beyond Planar Graphs: Introduction ⋮ Quantitative Restrictions on Crossing Patterns ⋮ 1-Planar Graphs ⋮ Algorithms for 1-Planar Graphs ⋮ 1-planarity testing and embedding: an experimental study
Cites Work
- Unnamed Item
- The structure of 1-planar graphs
- Upward drawings of triconnected digraphs.
- Optimal 1-planar graphs which triangulate other surfaces
- Graphs drawn with few crossings per edge
- On edge colorings of \(1\)-planar graphs
- Ein Sechsfarbenproblem auf der Kugel
- On the Computational Complexity of Upward and Rectilinear Planarity Testing
- Fáry’s Theorem for 1-Planar Graphs
- Re-embeddings of Maximum 1-Planar Graphs
- Right Angle Crossing Graphs and 1-Planarity
- On local properties of 1-planar graphs with high minimum degree
- Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
- Rectilinear drawings of graphs
- On Embedding a Graph in the Grid with the Minimum Number of Bends
- On the Density of Maximal 1-Planar Graphs
- Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
- Mathematical Foundations of Computer Science 2003
- Acyclic colouring of 1-planar graphs
This page was built for publication: A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
