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 @math 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 @math crossings, where @math is the maximum degree in G. This result implies an @math -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.
@cite_19: We give improved approximations for two classical embedding problems: (i) minimizing the number of crossings in a drawing on the plane of a bounded degree graph; and (ii) minimizing the VLSI layout area of a graph of maximum degree four. These improved algorithms can be applied to improve a variety of VLSI layout problems. Our results are as follows. (i) We compute a drawing on the plane of a bounded degree graph in which the sum of the numbers of vertices and crossings is O(log3 n) @math times the minimum layout area. This is an O(log2 n) improvement over the best known long-standing result.
@cite_31: 
@cite_32: This paper introduces a new divide-and-conquer framework for VLSI graph layout. Universally close upper and lower bounds are obtained for important cost functions such as layout area and propagation delay. The framework is also effectively used to design regular and configurable layouts, to assemble large networks of processor using restructurable chips, and to configure networks around faulty processors. It is also shown how good graph partitioning heuristics may be used to develop provably good layout strategy.
In their seminal paper, Leighton and Rao @cite_31 , combining their separator theorem with the framework of Bhatt and Leighton @cite_32 , gave the first non-trivial approximation algorithm for crossing number. More precisely, for a given bounded-degree graph @math their algorithm computes a drawing with at most @math crossings. This was later improved to @math by @cite_19 . Note that in general, these algorithms imply only a @math -approximation.