A general approximation result for n+cr(G).

Abstract: We give improved approximations for two classical embedding problems: (i) minimizing the number of crossings in a drawing of a bounded degree graph on the plane; and (ii) minimizing the VLSI layout area of a degree four graph. 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(log 3 n) times the optimal minimum sum. This is a logarithmic factor improvement relative to the best known result. (ii) We compute a VLSI layout of a degree four graph in a grid with constant aspect ratio the area of which is O(log 4 n) times the optimal minimum layout area. This is an O(log 2 n) improvement over the best known long standing result. 1 Introduction In this paper we study two related problems: (1) drawing a bounded degree graph on the plane with the fewest number of crossings of edges and (2) minimizat...

• Guy Even, Sudipto Guha, Baruch Schieber: Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas. SIAM J. Comput. 32(1): 231-252 (2002)

The planarization heuristic for crossing number

• Carsten Gutwenger, Petra Mutzel: An Experimental Study of Crossing Minimization Heuristics. Graph Drawing 2003: 13-24

In practice, the crossing minimization problem is solved heuristically using a 2-step planarization approach. In a first step, a small number of edges is deleted from G = (V,E) in order to obtain a planar graph P. In a second step, the edges are re-inserted into the planar graph P while trying to keep the number of crossings small.

Edge Re-insertion Strategies

Fixed Embedding. Also the edge re-insertion step is a NP-hard optimization problem [25]. The standard algorithm used in practice re-inserts the edges e1, e2, . . . , ek iteratively starting with a given planar embedding of G. The approach is based on the observation that an edge ei crosses an edge in P if and only if it uses an edge in the geometric dual graph of P. Hence, the problem of reinserting only one edge into P with a given planar embedding can be solved via a simple shortest-path computation in the extended dual graph of P. (We need to extend the dual graph in order to connect the end-vertices of ei with the dual graph.)

After each insertion step i, the crossings generated by edge ei are substituted by artificial vertices so that the resulting graph G ∪ {e1, . . . , ei} becomes planar again (i = 1, . . . , k). The theoretical worst case running time for inserting k edges of our implementation is O(k(|V | + |C|)), where C the number of crossings in the final drawing. In practice, it is much faster, since the update of the dual graphs are implemented efficiently.We denote this re-insertion method as FIX.

Variable Embedding. However, the quality of the resulting drawing highly depends on the chosen embedding for P. In [11], Gutwenger et al. have given a linear time algorithm based on the SPQR-tree data structure for inserting one edge into a planar graph P so that the number of crossings in P ∪{e} over the set of all possible planar embeddings of P is minimized. Our implementation has the same theoretical running time as the variant FIX. We denote this re-insertion method as VAR.

Constrained Crossing Minimization. Obviously, re-insertion of all edges at the same time will improve the solution. However, no practically efficient algorithm is known. The constrained crossing minimization problem asks for the minimum number of crossings obtained by a set of edges F when inserted into a planar graph P, while the embedding of P is not changed. The problem has been investigated in [20,25]. Experiments show that it can only be solved to provable optimality if there are less than 10 re-inserted edges — and even then, the running time is relatively high. Therefore, we did not include this method into our experiments.

Post-Processing Strategies. The idea of the post-processing strategies is to iteratively delete an edge from the drawing and to re-insert it again. Our strategies vary in the set and/or number of edges involved in the deletion and re-insertion process, and the order of processing them.

OGDF - Open Graph Drawing Framework

OGDF is a self-contained C++ class library for the automatic layout of diagrams. OGDF offers sophisticated algorithms and data structures to use within your own applications or scientific projects. The library is available under the GNU General Public License. OGDF is developed and supported by Technische Universität Dortmund, the Friedrich-Schiller-University Jena, the University of Cologne, and oreas GmbH.

Our goals for the Open Graph Drawing Framework (OGDF) were to transfer essential design concepts of AGD and to overcome its main deficiencies for use in academic research. The library provides:

• A wide range of graph drawing algorithms that allow to reuse and replace particular algorithm phases by using a dedicated module mechanism.
• Sophisticated data structures that are commonly used in graph drawing, equipped with rich public interfaces.
• Self-contained code that does not require any additional libraries (except for some optional branch-and-cut algorithms).
• Portable C++-code that supports the most important compilers for Linux, MacOS, and Windows operating systems.
• Open source code available under the terms of the GNU General Public License version 2 or version 3.