Logo

Login | Create Account

Exact Crossing Minimization

Buchheim, Christoph and Ebner, Dietmar and Jünger, Michael and Klau, Gunnar W. and Mutzel, Petra and Weiskircher, René (2006) Exact Crossing Minimization. [Conference Paper]

Full text not available from this repository.

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.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.420 Crossings
ID Code:678
Deposited By:GDEA, Administration
Deposited On:22 Feb 2006
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=3843&spage=37

Repository Staff Only: item control page

References

C. Batini, M. Talamo, and R. Tamassia.: Computer aided layout of entity-relationship diagrams. Journal of Systems and Software, 4:163--173, 1984.

S. N. Bhatt and F. T. Leighton.: A framework for solving VLSI graph layout problems. Journal of Computer and System Sciences, 28:300--343, 1984.

H. Bodlaender and A. Grigoriev.: Algorithms for graphs embeddable with few crossings per edge. Research Memoranda 036, Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization, 2004.

K. S. Booth and G. S. Lueker.: 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.

G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari, and F. Vargiu.An experimental comparison of four graph drawing algorithms. Computational Geometry: Theory and Applications, 7(5-6):303--325, 1997.

P. Eades and N. C. Wormald.: Edge crossings in drawings of bipartite graphs. Algorithmica, 11(4):379--403, 1994.

M. R. Garey and D. S. Johnson.: Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods, 4:312--316, 1983.

M.Grohe.: Computing crossing numbers in quadratic time. STOC 2001: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, 2001.

C. Gutwenger and P. Mutzel.: An experimental study of crossing minimization heuristics. In G. Liotta, editor, GD 2003: Proceedings of the 11th International Symposium on Graph Drawing, volume 2912 of LNCS, pages 13--24. Springer-Verlag, 2004.

R. K. Guy.: Crossing numbers of graphs. Graph Theory and Applications (Proceedings), Lecture Notes in Mathematics, pages 111--124. Springer-Verlag, 1972.

J. Hopcroft and R. Tarjan.: Efficient planarity testing. Journal of the ACM, 21(4):549--568, 1974.

M. Jünger and P. Mutzel.: Maximum planar subgraphs and nice embeddings: Practical layout tools. Algorithmica, 16(1):33--59, 1996.

J. Kratochvil.: String graphs. II.: Recognizing string graphs is NP-hard. Journal of Combinatorial Theory, Series B, 52(1):67--78, 1991.

P. Liu and R. Geldmacher.: On the deletion of nonplanar edges of a graph. Proceedings of the 10th Southeastern Conference on Combinatorics, Graph Theory, and Computing, pages 727--738, Boca Raton, FL, 1977.

S. Masuda, T. Kashiwabara, K. Nakajima, and T. Fujisawa.: On the NP-completeness of a computer network layout problem. Proceedings of the IEEE International Symposium on Circuits and Systems, pages 292--295, 1987.

S. Masuda, K. Nakajima, T. Kashiwabara, and T. Fujisawa.: Crossing minimization in linear embeddings of graphs. IEEE Transactions on Computers, 39(1):124--127, 1990.

J. Pach and G.Toth.: Graphs drawn with few crossings per edge. Combinatorica, 17(3):427--439, 1997.

H.C. Purchase.: Which aesthetic has the greatest effect on human understanding? Giuseppe Di Battista, editor, GD '97: Proceedings of the 5th International Symposium on Graph Drawing}, volume 1353 of LNCS, pages 248--261. Springer-Verlag, 1997

P. Turan.: A note of welcome. Journal of Graph Theory, 1:7--9, 1977.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.