A linear-time algorithm for testing full outer-2-planarity
From MaRDI portal
Publication:1727743
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
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
