A tighter insertion-based approximation of the crossing number

DOI10.1007/978-3-642-22006-7_11zbMATH Open1369.05042arXiv1104.5039OpenAlexW2973550843MaRDI QIDQ2012882FDOQ2012882

Authors: 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)

Abstract: Let G be a planar graph and F a set of additional edges not yet in G. The multiple edge insertion problem (MEI) asks for a drawing of G+F with the minimum number of pairwise edge crossings, such that the subdrawing of G is plane. Finding an exact solution to MEI is NP-hard for general F. We present the first polynomial time algorithm for MEI that achieves an additive approximation guarantee -- depending only on the size of F and the maximum degree of G, in the case of connected G. Our algorithm seems to be the first directly implementable one in that realm, too, next to the single edge insertion. It is also known that an (even approximate) solution to the MEI problem would approximate the crossing number of the F-almost-planar graph G+F, while computing the crossing number of G+F exactly is NP-hard already when |F|=1. Hence our algorithm induces new, improved approximation bounds for the crossing number problem of F-almost-planar graphs, achieving constant-factor approximation for the large class of such graphs of bounded degrees and bounded size of F.

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

Recommendations

• A tighter insertion-based approximation of the crossing number
• Inserting multiple edges into a planar graph
• On the Crossing Number of Almost Planar Graphs
• On graph crossing number and edge planarization
• Approximating the Crossing Number of Apex Graphs

zbMATH Keywords

planar graphcrossing numbermultiple edge insertionSPQR tree

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites Work

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

Cited In (21)

• Inserting an edge into a planar graph
• Crossing numbers and stress of random graphs
• Toroidal grid minors and stretch in embedded graphs
• A tighter insertion-based approximation of the crossing number
• Advances in the planarization method: effective multiple edge insertions
• Approximating the Crossing Number of Apex Graphs
• Inserting an edge into a planar graph
• Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics
• Title not available (Why is that?)
• Star-struck by fixed embeddings: modern crossing number heuristics
• Exact crossing number parameterized by vertex cover
• Inserting an edge into a geometric embedding
• On maximum common subgraph problems in series-parallel graphs
• Inserting Multiple Edges into a Planar Graph
• Parameterized analysis and crossing minimization problems
• Advances in the planarization method: effective multiple edge insertions
• An effective crossing minimisation heuristic based on star insertion
• Title not available (Why is that?)
• Vertex insertion approximates the crossing number of apex graphs
• Approximation Algorithms for Euler Genus and Related Problems
• On the bond polytope

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2012882)