A linear-time algorithm for testing full outer-2-planarity

DOI10.1016/j.dam.2018.08.018zbMath1405.05036OpenAlexW2898765768MaRDI QIDQ1727743

Seok-Hee Hong, Hiroshi Nagamochi

Publication date: 20 February 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2018.08.018

zbMATH Keywords

full-outer-2-planar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

The density of fan-planar graphs, Recognizing and embedding simple optimal 2-planar graphs, On RAC drawings of graphs with one bend per edge, Beyond Planar Graphs: Introduction, Algorithms for 1-Planar Graphs, 2-Layer k-Planar Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• New bounds on the maximum number of edges in \(k\)-quasi-planar graphs
• 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
• Fan-planarity: properties and complexity
• Algorithms for graphs embeddable with few crossings per edge
• Testing Full Outer-2-planarity in Linear Time
• Parameterized Complexity of 1-Planarity
• On the Number of Edges of Fan-Crossing Free Graphs
• Fáry’s Theorem for 1-Planar Graphs
• On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs
• The Straight-Line RAC Drawing Problem is NP-Hard
• Straight-Line Drawability of a Planar Graph Plus an Edge
• Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
• Rectilinear drawings of graphs
• Efficient Planarity Testing
• On-Line Planarity Testing
• The Number of Edges in $k$-Quasi-planar Graphs