A linear-time algorithm for testing outer-1-planarity

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

zbMATH Keywords

graph drawing1-planarity1-planar embedding1-planar graphsouter 1-planar graphs

Mathematics Subject Classification ID

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