2010/10/19 by Julia Chuzhoy, Chuzhoy, Julia, Yury Makarychev +3
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.1010.3976
openalex publication_date 2010/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(log2 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)⋅ k⋅ (k+OPT) crossings, where d is the maximum degree in G. This result implies an O(n⋅ \poly(d)⋅ log3/2n)-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.