Testing Full Outer-2-planarity in Linear Time

DOI10.1007/978-3-662-53174-7_29zbMath1417.05212OpenAlexW2487036166MaRDI QIDQ2827826

Seok-Hee Hong, Hiroshi Nagamochi

Publication date: 21 October 2016

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-53174-7_29

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Unnamed Item, On the Density of Non-simple 3-Planar Graphs, Gap-Planar Graphs, Beyond Outerplanarity, A heuristic approach towards drawings of graphs with high crossing resolution, A linear-time algorithm for testing full outer-2-planarity, On RAC drawings of graphs with one bend per edge, Gap-planar graphs, Testing Full Outer-2-planarity in Linear Time, $$\textit{\textbf{k}}$$-Planar Graphs

Cites Work

• Unnamed Item
• A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
• A linear-time algorithm for testing outer-1-planarity
• Drawing graphs with right angle crossings
• On the maximum number of edges in topological graphs with no four pairwise crossing edges
• Graphs drawn with few crossings per edge
• Quasi-planar graphs have a linear number of edges
• Algorithms for graphs embeddable with few crossings per edge
• Testing Full Outer-2-planarity in Linear Time
• Recognizing Outer 1-Planar Graphs in Linear Time
• On the Number of Edges of Fan-Crossing Free Graphs
• Fáry’s Theorem for 1-Planar Graphs
• Fan-Planar Graphs: Combinatorial Properties and Complexity Results
• On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs
• The Straight-Line RAC Drawing Problem is NP-Hard
• Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
• Rectilinear drawings of graphs
• On-Line Planarity Testing
• The Number of Edges in $k$-Quasi-planar Graphs