Exact Approaches to Multilevel Vertical Orderings

References

• Ahmed A, Fu X, Hong S-H, Nguyen QH, Xu K (2010) Visual analysis of history of World Cup: A dynamic network with dynamic hierarchy and geographic clustering. Proc. Visual Inform. Comm. Internat. [VINCI'2009] (Springer, New York), 25–39.Google Scholar
• Amaral ARS (2009) A new lower bound for the single row facility layout problem. Discrete Appl. Math. 157(1):183–190.Crossref, Google Scholar
• Anjos MF, Liers F (2012) Global approaches for facility layout and VLSI floorplanning. Anjos MF, Lasserre JB, Hillier FS, Price CC, eds. Handbook on Semidefinite, Conic and Polynomial Optimization, Internat. Ser. Oper. Res. and Management Sci., Vol. 166 (Springer, New York), 849–877.Crossref, Google Scholar
• Anjos MF, 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.Link, Google Scholar
• Buchheim C, Liers F, Oswald M (2010a) Speeding up IP-based algorithms for constrained quadratic 01 optimization. Math. Programming B 124(1–2):513–535.Crossref, Google Scholar
• Buchheim C, Wiegele A, Zheng L (2010b) Exact algorithms for the quadratic linear ordering problem. INFORMS J. Comput. 22(1):168–177.Link, Google Scholar
• Caprara A, Letchford AN, Salazar-González J-J (2011) Decorous lower bounds for minimum linear arrangement. INFORMS J. Comput. 23(1):26–40.Link, Google Scholar
• Chimani M, Hungerländer P (2011) Multilevel verticality optimization: Concept, strategies, and drawing scheme. Technical report, Computer Science, Algorithm Engineering Group, TR-FSUJ-CS-AE-11-01, Uni Jena, Jena, Germany.Google Scholar
• Chimani M, Hungerländer P, Jünger M, Mutzel P (2012) An SDP approach to multilevel crossing minimization. J. Experiment. Algorithmics 17(1):Article 3.3. Crossref, Google Scholar
• Christof T (1997) Low-dimensional 0/1-polytopes and branch-and-cut in combinatorial optimization. Ph.D. thesis, Ruprecht-Karls-Universität Heidelberg, Aachen, Germany.Google Scholar
• Christof T, Oswald M, Reinelt G (1998) Consecutive ones and a betweenness problem in computational biology. Proc. Conf. Integer Programming Combin. Optim. [IPCO'98], LNCS, Vol. 1412 (Springer, New York), 213–228.Crossref, Google Scholar
• Fischer I, Gruber G, Rendl F, Sotirov R (2006) Computational experience with a bundle method for semidefinite cutting plane relaxations of max-cut and equipartition. Math. Programming B 105(2–3):451–469.Crossref, Google Scholar
• Gange G, Stuckey P, Marriott K (2011) Optimal k-level planarization and crossing minimization. Brandes U, Cornelsen S, eds. Graph Drawing, Lecture Notes in Computer Science, Vol. 6502 (Springer, Berlin/Heidelberg), 238–249.Crossref, Google Scholar
• Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6):1115–1145.Crossref, Google Scholar
• Graphviz (2010) Graphviz gallery. http://www.graphviz.org/gallery.php.Google Scholar
• Healy P, Kuusik A (1999a) The vertex-exchange graph: A new concept for multilevel crossing minimisation. Proc. Sympos. Graph Drawing [GD'99], LNCS, Vol. 1731 (Springer, Berlin/Heidelberg), 205–216.Crossref, Google Scholar
• Healy P, Kuusik A (1999b) The vertex-exchange graph and its use in multilevel graph layout. Technical Report UL-CSIS-99-1, Department of Computer Science and Information Systems, University of Limerick, Ireland.Google Scholar
• Healy P, Kuusik A (2004) Algorithms for multilevel graph planarity testing and layout. Theoret. Comput. Sci. 320(2–3):331–344.Crossref, Google Scholar
• Helmberg C (2000) Fixing variables in semidefinite relaxations. SIAM J. Matrix Anal. Appl. 21(3):952–969.Crossref, Google Scholar
• Helmberg C, Rendl F, Vanderbei R, Wolkowicz H (1996) An interior-point method for semidefinite programming. SIAM J. Optim. 6(2):342–361.Crossref, Google Scholar
• Hungerländer P, Rendl F (2013) Semidefinite relaxations of ordering problems. Math. Programming B, ePub ahead of print January 4, http://link.springer.com/article/10.1007%2Fs10107-012-0627-7.Crossref, Google Scholar
• Jünger M, Mutzel P (1997) 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms. J. Graph Algorithms Appl. 1(1):1–25.Crossref, Google Scholar
• Jünger M, Lee EK, Mutzel P, Odenthal T (1997) A polyhedral approach to the multilayer crossing minimization problem. Proc. Sympos. Graph Drawing [GD'97], LNCS, Vol. 1353 (Springer, Berlin/Heidelberg), 13–24.Crossref, Google Scholar
• Lovász L, Schrijver A (1991) Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1(2):166–190.Crossref, Google Scholar
• May M, Szkatula K (1988) On the bipartite crossing number. Control Cybernetics 72:85–97.Google Scholar
• Mutzel P, Weiskircher R (1998) Two-layer planarization in graph drawing. Proc. Internat. Sympos. Algorithms Comput. [ISAAC'98], LNCS, Vol. 1533 (Springer, Berlin/Heidelberg), 69–78.Crossref, Google Scholar
• Nachmanson L, Pupyrev S, Kaufmann M (2010) Improving layered graph layouts with edge bundling. Proc. Sympos. Graph Drawing [GD'2010], LNCS, Vol. 6502 (Springer, Berlin/Heidelberg), 329–340.Google Scholar
• Purchase HC (1997) Which aesthetic has the greatest effect on human understanding? Proc. Sympos. Graph Drawing [GD'97], LNCS, Vol. 1353 (Springer, Berlin/Heidelberg), 248–259.Crossref, Google Scholar
• Rendl F, Rinaldi G, Wiegele A (2010) Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Math. Programming A 121(2):307–335.Crossref, Google Scholar
• Schwarz R (2010) A branch-and-cut algorithm with betweenness variables for the linear arrangement problems. Master's thesis, Universität Heidelberg, Germany.Google Scholar
• Seitz H (2010) Contributions to the minimum linear arrangement problem. Ph.D. thesis, University of Heidelberg,Germany.Google Scholar
• Shieh F, McCreary C (1996) Directed graphs drawing by clan-based decomposition. Proc. Sympos. Graph Drawing [GD'95], LNCS, Vol. 1027 (Springer, Berlin/Heidelberg), 472–482.Crossref, Google Scholar
• Sugiyama K, Tagawa S, Toda M (1981) Methods for visual understanding of hierarchical system structures. IEEE Trans. Systems, Man, Cybernetics 11(2):109–125.Crossref, Google Scholar
• Tucker AW (1960) On directed graphs and integer programs. IBM Mathematical Research Project, Technical report, Princeton University, Princeton, NJ.Google Scholar
• Younger DH (1963) Minimum feedback arc sets for a directed graph. IEEE Trans. Circuit Theory 10(2):238–245.Crossref, Google Scholar