skip to main content
research-article

An SDP approach to multi-level crossing minimization

Published: 13 September 2012 Publication History

Abstract

We present an approach based on semidefinite programs (SDP) to tackle the multi-level crossing minimization problem. We are given a layered graph (i.e., the graph's vertices are assigned to multiple parallel levels) and are asked for an ordering of the nodes on each level such that, when drawing the graph with straight lines, the resulting number of crossings is minimized. Solving this step is crucial in what is probably the most widely used graph drawing scheme, the Sugiyama framework.
The problem has received a lot of attention in both the fields of heuristics and exact methods. For a long time, integer linear programming (ILP) approaches were the only exact algorithms applicable, at least for small graphs. Recently, SDP formulations for the special case of two levels were proposed and dominated the ILP for dense instances.
In this article, we present a new SDP formulation for the general multi-level version that, for two levels, is even stronger than the aforementioned specialized SDP. As a by-product, we also obtain an SDP-based heuristic, which in practice always gives (near-)optimal solutions.
We conduct a large set of experiments, both on randomized and on real-world instances, and compare our approach to a state-of-the-art ILP-based branch-and-cut implementation. The SDP clearly dominates for denser graphs, while the ILP approach is usually faster for sparse instances. However, even for such sparse graphs, the SDP solves more instances to optimality than the ILP. In fact, there is no single instance that the ILP solved that the SDP did not. Overall, our experiments reveal that, for sparse graphs, one should usually try to find an optimal solution with the ILP first. If this approach does not solve the instance to optimality within reasonable time, the SDP still has a good chance to do so.
Being able to solve larger real-world instances than reported before, we are also able to evaluate heuristics for this problem. In this article, we do so for the traditional barycenter-heuristic (showing that it leaves a large gap to the true optimum) and the state-of-the-art upward-planarization method (showing that it is usually close to the optimum).

References

[1]
Anjos, M. F. and Vannelli, A. 2008. Computing globally optimal solutions for single-row layout problems using semidefinite programming and cutting planes. INFORMS J. Comput. 20, 4, 611--617.
[2]
Boyd, S. and Vandenberghe, L. 2004. Convex Optimization. Cambridge University Press, Cambridge, UK.
[3]
Buchheim, C., Wiegele, A., and Zheng, L. 2009. Exact algorithms for the quadratic linear ordering problem. INFORMS J. Comput. 168--177.
[4]
Chimani, M., Gutwenger, C., Mutzel, P., and Wong, H.-M. 2010a. Layer-free upward crossing minimization. ACM J. Exp. Algor. 15.
[5]
Chimani, M., Gutwenger, C., Mutzel, P., and Wong, H.-M. 2010b. Upward planarization layout. In Proceedings of the Symposium on Graph Drawing (GD'09). Lecture Notes in Computer Science, vol. 5849, Springer, 94--106.
[6]
De Simone, C. 1990. The cut polytope and the Boolean quadric polytope. Discrete Math. 79, 1, 71--75.
[7]
Deza, M. 1960. On the hamming geometry of unitary cubes. Doklady Akademii Nauk SSR 134, 1037--1040. {English translation in: Soviet Physics Doklady 5 (1961) 940--943}.
[8]
Deza, M. and Laurent, M. 1992a. Facets for the cut cone I. Math. Program. 56, 121--160.
[9]
Deza, M. and Laurent, M. 1992b. Facets for the cut cone II: clique-web inequalities. Math. Program. 56, 161--188.
[10]
Di Battista, G., Garg, A., Liotta, G., Parise, A., Tamassia, R., Tassinari, E., Vargiu, F., and Vismara, L. 2000. Drawing directed acyclic graphs: an experimental study. Int. J. Comput. Geom. Appl. 10, 6, 623--648.
[11]
Di Battista, G., Garg, A., Liotta, G., Tamassia, R., Tassinari, E., and Vargiu, F. 1997. An experimental comparison of four graph drawing algorithms. Comput. Geom. Theor. Appl. 7, 5-6, 303--325.
[12]
Dujmović, V., Fernau, H., and Kaufmann, M. 2008. Fixed parameter algorithms for one-sided crossing minimization revisited. J. Discrete Algor. 6, 2, 313--323.
[13]
Eades, P. and Wormald, N. C. 1994. Edge crossings in drawings of bipartite graphs. Algorithmica 11, 4, 379--403.
[14]
Eiglsperger, M., Kaufmann, M., and Eppinger, F. 2003. An approach for mixed upward planarization. J. Graph Algor. Appl. 7, 2, 203--220.
[15]
Fischer, I., Gruber, G., Rendl, F., and Sotirov, R. 2006. Computational experience with a bundle method for semidefinite cutting plane relaxations of max-cut and equipartition. Math. Program. 105, 451--469.
[16]
Gange, G., Stuckey, P. J., and Marriott, K. 2010. Optimal k-level planarization and crossing minimization. In Proceedings of the Symposium on Graph Drawing (GD'10). Lecture Notes in Computer Science, Springer.
[17]
Gansner, E. R., Koutsofios, E., North, S. C., and Vo, K. P. 1993. A technique for drawing directed graphs. IEEE Trans. Softw. Eng. 19, 3, 214--230.
[18]
Goemans, M. and Williamson, D. 1995. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115--1145.
[19]
Graphviz Oktober 2010. Graphviz gallery. http://www.graphviz.org/Gallery.php.
[20]
Healy, P. and Kuusik, A. 1999a. The vertex-exchange graph: a new concept for multilevel crossing minimisation. In Proceedings of the Symposium on Graph Drawing (GD'99). Lecture Notes in Computer Science, vol. 1731, Springer, 205--216.
[21]
Healy, P. and Kuusik, A. 1999b. The vertex-exchange graph and its use in multi-level graph layout. Tech. rep. UL-CSIS-99-1, Department of Computer Science and Information Systems, University of Limerick, Ireland.
[22]
Helmberg, C. 2000. Fixing variables in semidefinite relaxations. SIAM J. Matrix Anal. Appl. 21, 3, 952--969.
[23]
Helmberg, C., Rendl, F., Vanderbei, R., and Wolkowicz, H. 1996. An interior-point method for semidefinite programming. SIAM J. Optim. 6, 342--361.
[24]
Hiriart-Urruty, J.-B. and Lemarechal, C. 1993. Convex Analysis and Minimization Algorithms Vol. 1 and 2. Springer.
[25]
Hungerländer, P. 2011. Algorithms and applications for convex optimization. Ph.D. thesis, Alpen-Adria Universität Klagenfurt.
[26]
Hungerländer, P. and Rendl, F. 2011. Semidefinite relaxations of ordering problems. Math. Program. B. http://www.optimization-online.org/DB_HTML/2010/08/2696.html.
[27]
Jünger, M., Lee, E. K., Mutzel, P., and Odenthal, T. 1997. A polyhedral approach to the multi-layer crossing minimization problem. In Proceedings of the Symposium on Graph Drawing (GD'97). Lecture Notes in Computer Science, vol. 1353, Springer, 13--24.
[28]
Jünger, M. and Mutzel, P. 1997. 2-layer straightline crossing minimization: performance of exact and heuristic algorithms. J. Graph Algor. Appl. 1, 1--25.
[29]
Kelly, J. 1975. Hypermetric spaces. In The Geometry of Metric and Linear Spaces, L. Kelly, Ed., Lecture Notes in Mathematics. Springer, Berlin, 17--31.
[30]
Lovász, L. and Schrijver, A. 1991. Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1, 166--190.
[31]
Martí, R. and Laguna, M. 2003. Heuristics and meta-heuristics for 2-layer straight line crossing minimization. Discrete Appl. Math. 127, 3, 665--678.
[32]
May, M. and Szkatula, K. 1988. On the bipartite crossing number. Control and Cybernetics 72, 85--97.
[33]
Rendl, F., Rinaldi, G., and Wiegele, A. 2010. Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Math. Program. 212, 307--335.
[34]
Sherali, H. D. and Adams, W. P. 1990. A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3, 3, 411--430.
[35]
Shieh, F. and McCreary, C. 1996. Directed graphs drawing by clan-based decomposition. In Proceedings of the Symposium on Graph Drawing (GD'95). Lecture Notes in Computer Science, vol. 1027, Springer, 472--482.
[36]
Sugiyama, K., Tagawa, S., and Toda, M. 1981. Methods for visual understanding of hierarchical system structures. IEEE Trans. Syst. Man Cyber. 11, 2, 109--125.

Cited By

View all
  • (2021)Crossing Minimal Edge‐Constrained Layout Planning using Benders DecompositionProduction and Operations Management10.1111/poms.1344130:10(3429-3447)Online publication date: 1-Oct-2021
  • (2018)Minimizing the Number of Edges via Edge Concentration in Dense Layered GraphsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2016.253451922:6(1652-1661)Online publication date: 28-Dec-2018
  • (2014)An exact approach to upward crossing minimizationProceedings of the Meeting on Algorithm Engineering & Expermiments10.5555/2790174.2790182(73-85)Online publication date: 5-Jan-2014
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Journal of Experimental Algorithmics
ACM Journal of Experimental Algorithmics  Volume 17, Issue
2012
427 pages
ISSN:1084-6654
EISSN:1084-6654
DOI:10.1145/2133803
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 September 2012
Accepted: 01 May 2012
Revised: 01 November 2011
Received: 01 May 2011
Published in JEA Volume 17

Author Tags

  1. Exact multi-level crossing minimization
  2. SDP approach
  3. Sugiyama
  4. experimental evaluation

Qualifiers

  • Research-article
  • Research
  • Refereed

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)15
  • Downloads (Last 6 weeks)4
Reflects downloads up to 17 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2021)Crossing Minimal Edge‐Constrained Layout Planning using Benders DecompositionProduction and Operations Management10.1111/poms.1344130:10(3429-3447)Online publication date: 1-Oct-2021
  • (2018)Minimizing the Number of Edges via Edge Concentration in Dense Layered GraphsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2016.253451922:6(1652-1661)Online publication date: 28-Dec-2018
  • (2014)An exact approach to upward crossing minimizationProceedings of the Meeting on Algorithm Engineering & Expermiments10.5555/2790174.2790182(73-85)Online publication date: 5-Jan-2014
  • (2014)A linear edge kernel for two-layer crossing minimizationTheoretical Computer Science10.1016/j.tcs.2014.06.009554:C(74-81)Online publication date: 16-Oct-2014
  • (2013)Exact Approaches to Multilevel Vertical OrderingsINFORMS Journal on Computing10.1287/ijoc.1120.052525:4(611-624)Online publication date: Nov-2013
  • (2013)An Exact Approach for the Combined Cell Layout ProblemOperations Research Proceedings 201210.1007/978-3-319-00795-3_40(275-281)Online publication date: 28-Nov-2013

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media