Towards Better Approximation of Graph Crossing Number
share
Graph Crossing Number is a fundamental problem with various applications. In this problem, the goal is to draw an input graph G in the plane so as to minimize the number of crossings between the images of its edges. Despite extensive work, non-trivial approximation algorithms are only known for bounded-degree graphs. Even for this special case, the best current algorithm achieves a Õ(√(n))-approximation, while the best current negative result is APX-hardness. All current approximation algorithms for the problem build on the same paradigm: compute a set E' of edges (called a planarizing set) such that G∖ E' is planar; compute a planar drawing of G∖ E'; then add the drawings of the edges of E' to the resulting drawing. Unfortunately, there are examples of graphs, in which any implementation of this method must incur Ω (OPT^2) crossings, where OPT is the value of the optimal solution. This barrier seems to doom the only known approach to designing approximation algorithms for the problem, and to prevent it from yielding a better than O(√(n))-approximation. In this paper we propose a new paradigm that allows us to overcome this barrier. We show an algorithm that, given a bounded-degree graph G and a planarizing set E' of its edges, computes another set E” with E'⊆ E”, such that |E”| is relatively small, and there exists a near-optimal drawing of G in which only edges of E” participate in crossings. This allows us to reduce the Crossing Number problem to Crossing Number with Rotation System – a variant in which the ordering of the edges incident to every vertex is fixed as part of input. We show a randomized algorithm for this new problem, that allows us to obtain an O(n^1/2-ϵ)-approximation for Crossing Number on bounded-degree graphs, for some constant ϵ>0.
READ FULL TEXT