Abstract
The crossing number problem is to find the smallest number of edge crossings necessary when drawing a graph into the plane. Eventhough the problem is NP-hard, we are interested in practically efficient algorithms to solve the problem to provable optimality. In this paper, we present a novel integer linear programming (ILP) formulation for the crossing number problem. The former formulation [4] had to transform the crossing number polytope into a higher-dimensional polytope. The key idea of our approach is to directly consider the natural crossing number polytope and cut it with multiple linear-ordering polytopes. This leads to a more compact formulation, both in terms of variables and constraints.
We describe a Branch-and-Cut algorithm, together with a combinatorial column generation scheme, in order to solve the crossing number problem to provable optimality. Our experiments show that the new approach is more effective than the old one, even when considering a heavily improved version of the former formulation (also presented in this paper). For the first time, we are able to solve graphs with a crossing number of up to 37.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: algorithms for the visualization of graphs. Prentice-Hall, Englewood Cliffs (1999)
Di Battista, G., Garg, A., Liotta, G., Tamassia, R., Tassinari, E., Vargiu, F.: An experimental comparison of four graph drawing algorithms. Comput. Geom. Theory Appl. 7(5-6), 303–325 (1997)
Boyer, J.M., Myrvold, W.J.: On the cutting edge: Simplified O(n) planarity by edge addition. Journal of Graph Algorithms an Applications 8(3), 241–273 (2004)
Buchheim, C., Chimani, M., Ebner, D., Gutwenger, C., Jünger, M., Klau, G.W., Mutzel, P., Weiskircher, R.: A branch-and-cut approach to the crossing number problem. Discrete Optimization 5, 373–388 (2008); (Memory of George B. Dantzig)
Buchheim, C., Jünger, M., Menze, A., Percan, M.: Bimodal crossing minimization. In: Chen, D.Z., Lee, D.T. (eds.) COCOON 2006. LNCS, vol. 4112, pp. 497–506. Springer, Heidelberg (2006)
Chimani, M., Gutwenger, C.: Algorithms for the hypergraph and the minor crossing number problems. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol. 4835, pp. 184–195. Springer, Heidelberg (2007)
Chimani, M., Gutwenger, C.: Non-planar core reduction of graphs. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 223–234. Springer, Heidelberg (2006)
Chimani, M., Gutwenger, C., Mutzel, P.: Experiments on exact crossing minimization using column generation. In: Àlvarez, C., Serna, M. (eds.) WEA 2006. LNCS, vol. 4007, pp. 303–315. Springer, Heidelberg (2006)
Chimani, M., Jünger, M., Schulz, M.: Crossing minimization meets simultaneous drawing. In: Proc. IEEE PacificVis 2008 (2008)
Chimani, M., Mutzel, P., Schmidt, J.M.: Efficient extraction of multiple kuratowski subdivisions. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 159–170. Springer, Heidelberg (2008)
Gutwenger, C., Mutzel, P.: An experimental study of crossing minimization heuristics. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 13–24. Springer, Heidelberg (2004)
Gutwenger, C., Mutzel, P., Weiskircher, R.: Inserting an edge into a planar graph. Algorithmica 41(4), 289–308 (2005)
Kleitman, D.J.: The crossing number of K 5,n . J. Comb. Theory 9, 315–323 (1970)
Kleitman, D.J.: A note on the parity of the number of crossings of a graph. J. Comb. Theory, Ser. B 21(1), 88–89 (1976)
Kratochvíl, J.: String graphs II: Recognizing string graphs is NP-hard. J. Combin. Theory Ser. B 52, 67–78 (1991)
Kuratowski, C.: Sur le problème des courbes gauches en topologie. Fund. Math. 15, 271–283 (1930)
OGDF – Open Graph Drawing Framework (2008), http://www.ogdf.net
Pach, J., Tóth, G.: Which crossing number is it anyway? J. Comb. Theory Ser. B 80(2), 225–246 (2000)
Schaefer, M., Sedgwick, E., Štefankovič, D.: Recognizing string graphs in NP. Journal of Computer and System Sciences 67(2), 365–380 (2003)
Vrt’o, I.: Crossing numbers of graphs: A bibliography (2007), ftp://ftp.ifi.savba.sk/pub/imrich/crobib.pdf
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chimani, M., Mutzel, P., Bomze, I. (2008). A New Approach to Exact Crossing Minimization. In: Halperin, D., Mehlhorn, K. (eds) Algorithms - ESA 2008. ESA 2008. Lecture Notes in Computer Science, vol 5193. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87744-8_24
Download citation
DOI: https://doi.org/10.1007/978-3-540-87744-8_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-87743-1
Online ISBN: 978-3-540-87744-8
eBook Packages: Computer ScienceComputer Science (R0)