Experiments on Exact Crossing Minimization Using Column Generation

  • Markus Chimani
  • Carsten Gutwenger
  • Petra Mutzel
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4007)


The crossing number of a graph G is the smallest number of edge crossings in any drawing of G into the plane. Recently, the first branch-and-cut approach for solving the crossing number problem has been presented in [3]. Its major drawback was the huge number of variables out of which only very few were actually used in the optimal solution. This restricted the algorithm to rather small graphs with low crossing number.

In this paper we discuss two column generation schemes; the first is based on traditional algebraic pricing, and the second uses combinatorial arguments to decide whether and which variables need to be added. The main focus of this paper is the experimental comparison between the original approach, and these two schemes. We also compare these new results to the solutions of the best known crossing number heuristic.


Column Generation Heuristic Solution Graph Draw Edge Crossing Primal Heuristic 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Batini, C., Talamo, M., Tamassia, R.: Computer aided layout of entity-relationship diagrams. Journal of Systems and Software 4, 163–173 (1984)CrossRefGoogle Scholar
  2. 2.
    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 (submitted for publication)Google Scholar
  3. 3.
    Buchheim, C., Ebner, D., Jünger, M., Klau, G.W., Mutzel, P., Weiskircher, R.: Exact crossing minimization. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, Springer, Heidelberg (2006)CrossRefGoogle Scholar
  4. 4.
    Dantzig, G.B., Wolfe, P.: Decomposition principle for linear programs. Operations Research 8, 101–111 (1960)CrossRefzbMATHGoogle Scholar
  5. 5.
    Di Battista, G., Garg, A., Liotta, G., Tamassia, R., Tassinari, E., Vargiu, F.: An experimental comparison of four graph drawing algorithms. Computational Geometry: Theory and Applications 7(5-6), 303–325 (1997)MathSciNetzbMATHGoogle Scholar
  6. 6.
    Di Battista, G., Tamassia, R.: On-line maintanance of triconnected components with SPQR-trees. Algorithmica 15, 302–318 (1996)CrossRefMathSciNetzbMATHGoogle Scholar
  7. 7.
    Gutwenger, C., Chimani, M.: Non-planar core reduction of graphs. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, Springer, Heidelberg (2006)CrossRefGoogle Scholar
  8. 8.
    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)CrossRefGoogle Scholar
  9. 9.
    Jünger, M., Thienel, S.: The ABACUS system for branch-and-cut-and-price-algorithms in integer programming and combinatorial optimization. Software: Practice & Experience 30(11), 1325–1352 (2000)CrossRefzbMATHGoogle Scholar
  10. 10.
    Kratochvíl, J.: String graphs. II.: Recognizing string graphs is NP-hard. Journal of Combinatorial Theory, Series B 52(1), 67–78 (1991)CrossRefMathSciNetzbMATHGoogle Scholar
  11. 11.
    OGDF – Open Graph Drawing Framework. University of Dortmund, Chair of Algorithm Engineering and Systems Analysis. Web site under constructionGoogle Scholar
  12. 12.
    Purchase, H.C.: Which aesthetic has the greatest effect on human understanding? In: DiBattista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 248–261. Springer, Heidelberg (1997)CrossRefGoogle Scholar
  13. 13.
    Turán, P.: A note of welcome. Journal of Graph Theory 1, 7–9 (1977)CrossRefGoogle Scholar
  14. 14.
    Imrich Vrto. Crossing numbers of graphs: A bibliography,
  15. 15.
    Williamson, S.G.: Depth-first search and Kuratowski subgraphs. Journal of the ACM 31(4), 681–693 (1984)CrossRefzbMATHGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Markus Chimani
    • 1
  • Carsten Gutwenger
    • 1
  • Petra Mutzel
    • 1
  1. 1.Department of Computer ScienceUniversity of DortmundGermany

Personalised recommendations