A Linear-Time Algorithm for Finding Induced Planar Subgraphs
From MaRDI portal
Publication:5140735
DOI10.4230/LIPIcs.SEA.2018.23zbMath1493.68270OpenAlexW2811281603MaRDI QIDQ5140735
No author found.
Publication date: 16 December 2020
Full work available at URL: http://drops.dagstuhl.de/opus/volltexte/2018/8958/pdf/LIPIcs-SEA-2018-23.pdf/
Analysis of algorithms (68W40) 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)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Regular graphs with small skewness and crossing numbers
- The node-deletion problem for hereditary properties is NP-complete
- Algorithms for drawing graphs: An annotated bibliography
- Maximum planar subgraphs and nice embeddings: Practical layout tools
- Planarization and fragmentability of some classes of graphs
- The Crossing-Angle Resolution in Graph Drawing
- Bar 1-Visibility Graphs and their relation to other Nearly Planar Graphs
- On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
- On the Crossing Number of Almost Planar Graphs
- Crossing and Weighted Crossing Number of Near-Planar Graphs
- Node-Deletion NP-Complete Problems
- A GRASP for graph planarization
- The approximation of maximum subgraph problems
- Bar k-Visibility Graphs
- Approximation Algorithms for the Maximum Induced Planar and Outerplanar Subgraph Problems
- Depth-First Search and Linear Graph Algorithms
- Harmonic functions on planar and almost planar graphs and manifolds, via circle packings
This page was built for publication: A Linear-Time Algorithm for Finding Induced Planar Subgraphs