Abstract
The crossing number of a graph is the minimum number of edge crossings in any drawing of the graph into the plane. This very basic property has been studied extensively in the literature from a theoretic point of view and many bounds exist for a variety of graph classes. In this paper, we present the first algorithm able to compute the crossing number of general sparse graphs of moderate size and present computational results on a popular benchmark set of graphs. The approach uses a new integer linear programming formulation of the problem combined with strong heuristics and problem reduction techniques. This enables us to compute the crossing number for 91 percent of all graphs on up to 40 nodes in the benchmark set within a time limit of five minutes per graph.
Chapter PDF
Similar content being viewed by others
Keywords
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.
References
Batini, C., Talamo, M., Tamassia, R.: Computer aided layout of entity-relationship diagrams. Journal of Systems and Software 4, 163–173 (1984)
Bhatt, S.N., Leighton, F.T.: A framework for solving VLSI graph layout problems. Journal of Computer and System Sciences 28, 300–343 (1984)
Bodlaender, H., Grigoriev, A.: Algorithms for graphs embeddable with few crossings per edge. Research Memoranda 036, Maastricht: METEOR, Maastricht Research School of Economics of Technology and Organization (2004)
Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences 13(3), 335–379 (1976)
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)
Eades, P., Wormald, N.C.: Edge crossings in drawings of bipartite graphs. Algorithmica 11(4), 379–403 (1994)
Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods 4, 312–316 (1983)
Grohe, M.: Computing crossing numbers in quadratic time. In: STOC 2001: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (2001)
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)
Guy, R.K.: Crossing numbers of graphs. In: Graph Theory and Applications (Proceedings). Lecture Notes in Mathematics, pp. 111–124. Springer, Heidelberg (1972)
Hopcroft, J., Tarjan, R.: Efficient planarity testing. Journal of the ACM 21(4), 549–568 (1974)
Jünger, M., Mutzel, P.: Maximum planar subgraphs and nice embeddings: Practical layout tools. Algorithmica 16(1), 33–59 (1996)
Kratochvíl, J.: String graphs. II.: Recognizing string graphs is NP-hard. Journal of Combinatorial Theory, Series B 52(1), 67–78 (1991)
Liu, P., Geldmacher, R.: On the deletion of nonplanar edges of a graph. In: Proceedings of the 10th Southeastern Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, FL, pp. 727–738 (1977)
Masuda, S., Kashiwabara, T., Nakajima, K., Fujisawa, T.: On the NP-completeness of a computer network layout problem. In: Proceedings of the IEEE International Symposium on Circuits and Systems, pp. 292–295 (1987)
Masuda, S., Nakajima, K., Kashiwabara, T., Fujisawa, T.: Crossing minimization in linear embeddings of graphs. IEEE Transactions on Computers 39(1), 124–127 (1990)
Pach, J., Tóth, G.: Graphs drawn with few crossings per edge. Combinatorica 17(3), 427–439 (1997)
Purchase, H.C.: Which aesthetic has the greatest effect on human understanding? In: Di Battista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 248–261. Springer, Heidelberg (1997)
Turán, P.: A note of welcome. Journal of Graph Theory 1, 7–9 (1977)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Buchheim, C., Ebner, D., Jünger, M., Klau, G.W., Mutzel, P., Weiskircher, R. (2006). Exact Crossing Minimization. In: Healy, P., Nikolov, N.S. (eds) Graph Drawing. GD 2005. Lecture Notes in Computer Science, vol 3843. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11618058_4
Download citation
DOI: https://doi.org/10.1007/11618058_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-31425-7
Online ISBN: 978-3-540-31667-1
eBook Packages: Computer ScienceComputer Science (R0)