The Constrained Crossing Minimization Problem

Mutzel, Petra and Ziegler, Thomas (1999) The Constrained Crossing Minimization Problem. In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999, Štirín Castle, Czech Republic , pp. 175-185 (Official URL: http://dx.doi.org/10.1007/3-540-46648-7_18).

Full text not available from this repository.

Abstract

In this paper we consider the constrained crossing minimization problem defined as follows. Given a connected planar graph G = (V,E), a combinatorial embedding \Pi(G) of G, and a set of pairwise distinct edges F \subseteq V \times V, find a drawing of G'=(V, E \cup F) such that the combinatiorial embedding \Pi(G) of G is preserved and the number of edge crossings is minimized. The constrained crossing minimization problem arises in the graph drawing method based on planarization. In [4] we have shown that we can formulate the constrained crossing minimization problem as an |F|-pairs shortest walks problem, where we want to minimize the sum of the lenghts of the walks plus the number of crossings between the walks. Here we present an integer linear programming formulation (ILP) for the shortest crossing walks problem. Furthermore, we will present additional valid inequalities that strengthen the formulation. Based on our results we have designed and implemented a branch and cut algorithm. Our computational experiments for the constrained crossing minimization problem on a bechmark set of graphs ([1]) are encouraging. This is the first time that practical instances of the constrained crossing minimization problem can be solved to provable optimality.

Item Type:Conference Paper
Additional Information:10.1007/3-540-46648-7_18
Classifications:G Algorithms and Complexity > G.999 Others
M Methods > M.600 Planar
G Algorithms and Complexity > G.840 Planarization
G Algorithms and Complexity > G.420 Crossings
ID Code:326

Repository Staff Only: item control page

References

G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari, and F. Vargiu. An experimental comparison of four graph drawing algorithms. Comput. Geom. Theory Appl., 7:303-326, 1997.

M. R. Garey and D. S. Johnson. Crossing Number is NP-Complete. SIAM J. Alg. Disc. Meth., Vol. 4, No. 3: 312-316, 1983.

S. Masuda, K. Nakajima, T. Kashiwabara, and T. Fujisawa. Crossing Minimization in Linear Embeddings of Graphs. In: IEEE Transactions on Computers, Vol. 39, No. 1: 124-127, 1990.

P. Mutzel and T. Ziegler. The Constrained Crossing Minimization Problem - A First Approach. In: P. Kall, H.-J. Lüthi (Eds.): Operations Research Proceedings 1998, Springer-Verlag, pp. 125-134, 1999.

P. Mutzel and T. Ziegler. The Constrained Crossing Minimization Problem. Forthcoming Technical Report, MPI Informatik, Saarbrücken, Germany, 1999.

K. Mehlhorn and S. Näher. LEDA: A platform for combinatorial and geometric computing. Comm. Assoc. Comput. Mach., 38:96-102, 1995.

M. Jünger and S. Thienel. Introduction to ABACUS - A Branch-And-CUt System. Technical Report No. 97.263, Institut für Informatik, Universität zu Köln, 1997, to appear in Operations Research Letters, 1999.