A linear-time algorithm for testing outer-1-planarity
From MaRDI portal
Publication:494794
DOI10.1007/s00453-014-9890-8zbMath1319.68158OpenAlexW2159869336WikidataQ62042391 ScholiaQ62042391MaRDI QIDQ494794
Seok-Hee Hong, Peter Eades, Yusuke Suzuki, Pascal Schweitzer, Naoki Katoh, Giuseppe Liotta
Publication date: 2 September 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-014-9890-8
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, An annotated bibliography on 1-planarity, \(\mathsf{NIC}\)-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, A linear-time algorithm for testing full outer-2-planarity, Re-embedding a 1-plane graph for a straight-line drawing in linear time, Characterizing and recognizing 4-map 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, Testing Full Outer-2-planarity in Linear Time, Beyond Planar Graphs: Introduction, Algorithms for 1-Planar Graphs, 1-planarity testing and embedding: an experimental study, 2-Layer k-Planar Graphs
Cites Work
- 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
- Drawing outerplanar graphs using three edge lengths
- The structure of 1-planar graphs
- Optimal 1-planar graphs which triangulate other surfaces
- The book thickness of a graph
- Graphs drawn with few crossings per edge
- On-line maintenance of triconnected components with SPQR-trees
- Ein Sechsfarbenproblem auf der Kugel
- Algorithms for graphs embeddable with few crossings per edge
- Graph Drawings with One Bend and Few Slopes
- Parameterized Complexity of 1-Planarity
- A Linear-Time Algorithm for Testing Outer-1-Planarity
- Recognizing Outer 1-Planar Graphs in Linear Time
- Fáry’s Theorem for 1-Planar Graphs
- Simpler Algorithms for Testing Two-Page Book Embedding of Partitioned Graphs
- Re-embeddings of Maximum 1-Planar Graphs
- Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
- Rectilinear drawings of graphs
- Dividing a Graph into Triconnected Components
- Testing Maximal 1-Planarity of Graphs with a Rotation System in Linear Time
- h-Quasi Planar Drawings of Bounded Treewidth Graphs in Linear Area
- EVERY OUTER-1-PLANE GRAPH HAS A RIGHT ANGLE CROSSING DRAWING
- Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
- Mathematical Foundations of Computer Science 2003
