Non-planar core reduction of graphs
From MaRDI portal
Publication:1011763
DOI10.1016/j.disc.2007.12.078zbMath1176.05077OpenAlexW1976060438MaRDI QIDQ1011763
Carsten Gutwenger, Markus Chimani
Publication date: 9 April 2009
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2007.12.078
thicknesscrossing numberskewnesspreprocessingcoarsenessgraph reductionlinear time complexity algorithm
Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (9)
Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics ⋮ Star-struck by fixed embeddings: modern crossing number heuristics ⋮ There are no cubic graphs on 26 vertices with crossing number 10 or 11 ⋮ A Note on the Practicality of Maximal Planar Subgraph Algorithms ⋮ Unnamed Item ⋮ Crossing number additivity over edge cuts ⋮ A note on the crossing number of the cone of a graph ⋮ Unnamed Item ⋮ On the skewness of Cartesian products with trees
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Additivity of the crossing number of graphs with connectivity 2
- A branch-and-cut approach to the crossing number problem
- Analysis of heuristics for finding a maximum weight planar subgraph
- Parallel concepts in graph theory
- The thickness of graphs: A survey
- Skewness of graphs with small cutsets
- Inserting an edge into a planar graph
- On-line maintenance of triconnected components with SPQR-trees
- Maximum planar subgraphs and nice embeddings: Practical layout tools
- Reduction tests for the prize-collecting Steiner problem
- An experimental comparison of four graph drawing algorithms.
- Planarizing Graphs - A Survey and Annotated Bibliography
- Crossing Number is NP-Complete
- On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
- On the Minimum Cut of Planarizations
- Determining the thickness of graphs is NP-hard
- Efficient Planarity Testing
- THE THICKNESS OF AN ARBITRARY COMPLETE GRAPH
- A Better Approximation Algorithm for Finding Planar Subgraphs
- An $O(m\log n)$-Time Algorithm for the Maximal Planar Subgraph Problem
- An efficient graph planarization two‐phase heuristic
- On Cotree-Critical and DFS Cotree-Critical Graphs
- On-Line Planarity Testing
- Dividing a Graph into Triconnected Components
- Graph Drawing
- Experiments on Exact Crossing Minimization Using Column Generation
- The Thickness of the Complete Graph
- A coarseness conjecture of Erdös
- The Coarseness of the Complete Graph
- The Coarseness of the Complete Bipartite Graph
- Computing and Combinatorics
- On a problem of P. Turan concerning graphs
- Graph Drawing
This page was built for publication: Non-planar core reduction of graphs
