Computer Science – Data Structures and Algorithms
Scientific paper
2010-10-19
Computer Science
Data Structures and Algorithms
Scientific paper
Given an n-vertex graph G, a drawing of G in the plane is a mapping of its vertices into points of the plane, and its edges into continuous curves, connecting the images of their endpoints. A crossing in such a drawing is a point where two such curves intersect. In the Minimum Crossing Number problem, the goal is to find a drawing of G with minimum number of crossings. The value of the optimal solution, denoted by OPT, is called the graph's crossing number. This is a very basic problem in topological graph theory, that has received a significant amount of attention, but is still poorly understood algorithmically. The best currently known efficient algorithm produces drawings with $O(\log^2 n)(n + OPT)$ crossings on bounded-degree graphs, while only a constant factor hardness of approximation is known. A closely related problem is Minimum Edge Planarization, in which the goal is to remove a minimum-cardinality subset of edges from G, such that the remaining graph is planar. Our main technical result establishes the following connection between the two problems: if we are given a solution of cost k to the Minimum Edge Planarization problem on graph G, then we can efficiently find a drawing of G with at most $\poly(d)\cdot k\cdot (k+OPT)$ crossings, where $d$ is the maximum degree in G. This result implies an $O(n\cdot \poly(d)\cdot \log^{3/2}n)$-approximation for Minimum Crossing Number, as well as improved algorithms for special cases of the problem, such as, for example, k-apex and bounded-genus graphs.
Chuzhoy Julia
Makarychev Yury
Sidiropoulos Anastasios
No associations
LandOfFree
On Graph Crossing Number and Edge Planarization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Graph Crossing Number and Edge Planarization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Graph Crossing Number and Edge Planarization will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-269384