1-planarity testing and embedding: an experimental study
From MaRDI portal
Publication:2088879
DOI10.1016/j.comgeo.2022.101900zbMath1498.05260OpenAlexW4281904075WikidataQ114195494 ScholiaQ114195494MaRDI QIDQ2088879
Fabrizio Montecchiani, Carla Binucci, Walter Didimo
Publication date: 6 October 2022
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.comgeo.2022.101900
Analysis of algorithms and problem complexity (68Q25) 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) Density (toughness, etc.) (05C42)
Uses Software
Cites Work
- Unnamed Item
- Outer 1-planar graphs
- 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
- Ortho-polygon visibility representations of embedded graphs
- An experimental study of a 1-planarity testing and embedding algorithm
- Graphs drawn with few crossings per edge
- Diameter and treewidth in minor-closed graph families
- Recognizing optimal 1-planar graphs in linear time
- Characterizing and recognizing 4-map graphs
- Inserting an edge into a planar graph
- Embedding-preserving rectangle visibility representations of nonplanar graphs
- Fan-planarity: properties and complexity
- On RAC drawings of 1-planar graphs
- An annotated bibliography on 1-planarity
- On the recognition of fan-planar and maximal outer-fan-planar graphs
- The book thickness of 1-planar graphs is constant
- Algorithms for graphs embeddable with few crossings per edge
- An experimental comparison of four graph drawing algorithms.
- Local tree-width, excluded minors, and approximation algorithms
- Straight-Line Grid Drawings of 3-Connected 1-Planar Graphs
- Fáry’s Theorem for 1-Planar Graphs
- 1-Visibility Representations of 1-Planar Graphs
- Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time
- A New Approach to Exact Crossing Minimization
- Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
- Guest Editors' Foreword and Overview
- Parameterized Complexity of 1-Planarity
- Algorithms for 1-Planar Graphs
- Beyond Planar Graphs
- Planar Graphs Have Bounded Queue-Number
- 1-Planarity of Graphs with a Rotation System
- Graph Drawing
- Listing All Maximal Cliques in Large Sparse Real-World Graphs
- Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
- Advances in the Planarization Method: Effective Multiple Edge Insertions
- Ortho-polygon visibility representations of 3-connected 1-plane graphs
- Crossing numbers of beyond-planar graphs
