A tighter insertion-based approximation of the crossing number

DOI10.1007/s10878-016-0030-zzbMath1369.05042arXiv1104.5039OpenAlexW2973550843MaRDI QIDQ2012882

Markus Chimani, Petr Hliněný

Publication date: 3 August 2017

Published in: Journal of Combinatorial Optimization, Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1104.5039

zbMATH Keywords

crossing numberplanar graphmultiple edge insertionSPQR tree

Mathematics Subject Classification ID

Trees (05C05) 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) Approximation algorithms (68W25)

Related Items (16)

Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics ⋮ Star-struck by fixed embeddings: modern crossing number heuristics ⋮ Parameterized analysis and crossing minimization problems ⋮ On maximum common subgraph problems in series-parallel graphs ⋮ Approximation Algorithms for Euler Genus and Related Problems ⋮ On the bond polytope ⋮ Inserting Multiple Edges into a Planar Graph ⋮ Unnamed Item ⋮ Exact crossing number parameterized by vertex cover ⋮ Crossing numbers and stress of random graphs ⋮ Vertex insertion approximates the crossing number of apex graphs ⋮ A tighter insertion-based approximation of the crossing number ⋮ Toroidal grid minors and stretch in embedded graphs ⋮ Advances in the Planarization Method: Effective Multiple Edge Insertions ⋮ Unnamed Item ⋮ An effective crossing minimisation heuristic based on star insertion

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Crossing number and weighted crossing number of near-planar graphs
• On the complexity of embedding planar graphs to minimize certain distance measures
• Vertex insertion approximates the crossing number of apex graphs
• A framework for solving VLSI graph layout problems
• The crossing number of a projective graph is quadratic in the face-width
• Inserting an edge into a planar graph
• A tighter insertion-based approximation of the crossing number
• The crossing number of a projective graph is quadratic in the face–width
• On the Crossing Number of Almost Planar Graphs
• Crossing and Weighted Crossing Number of Near-Planar Graphs
• Approximating the Crossing Number of Apex Graphs
• Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas
• On-Line Planarity Testing
• Dividing a Graph into Triconnected Components
• Graph Drawing
• Crossing minimization in linear embeddings of graphs
• Approximating the Crossing Number of Toroidal Graphs
• Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
• Adding one edge to planar graphs makes crossing number hard
• An algorithm for the graph crossing number problem
• Advances in the Planarization Method: Effective Multiple Edge Insertions
• Expander flows, geometric embeddings and graph partitioning

This page was built for publication: A tighter insertion-based approximation of the crossing number