{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:26:29Z","timestamp":1750307189208,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2012,7,1]],"date-time":"2012-07-01T00:00:00Z","timestamp":1341100800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>\n          <jats:p>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).<\/jats:p>","DOI":"10.1145\/2133803.2330084","type":"journal-article","created":{"date-parts":[[2012,10,16]],"date-time":"2012-10-16T12:50:57Z","timestamp":1350391857000},"source":"Crossref","is-referenced-by-count":4,"title":["An SDP approach to multi-level crossing minimization"],"prefix":"10.1145","volume":"17","author":[{"given":"Markus","family":"Chimani","sequence":"first","affiliation":[{"name":"Friedrich-Schiller-University of Jena, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philipp","family":"Hungerl\u00e4nder","sequence":"additional","affiliation":[{"name":"Alpen-Adria Universit\u00e4t Klagenfurt, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"J\u00fcnger","sequence":"additional","affiliation":[{"name":"University of Cologne, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petra","family":"Mutzel","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Dortmund, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,9,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1080.0270"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Boyd S. and Vandenberghe L. 2004. Convex Optimization. Cambridge University Press Cambridge UK.   Boyd S. and Vandenberghe L. 2004. Convex Optimization. Cambridge University Press Cambridge UK.","DOI":"10.1017\/CBO9780511804441"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1090.0318"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1671970.1671975"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11805-0_11"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90056-N"},{"key":"e_1_2_1_7_1","first-page":"1037","article-title":"On the hamming geometry of unitary cubes","volume":"134","author":"Deza M.","year":"1960","unstructured":"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}. 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}.","journal-title":"Doklady Akademii Nauk SSR"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580897"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580898"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195900000358"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(96)00005-3"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2006.12.008"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187020"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00067"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0661-9"},{"volume-title":"Proceedings of the Symposium on Graph Drawing (GD'10)","author":"Gange G.","key":"e_1_2_1_16_1","unstructured":"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. 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."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.221135"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_2_1_19_1","unstructured":"Graphviz Oktober 2010. Graphviz gallery. http:\/\/www.graphviz.org\/Gallery.php.  Graphviz Oktober 2010. Graphviz gallery. http:\/\/www.graphviz.org\/Gallery.php."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46648-7_21"},{"key":"e_1_2_1_21_1","unstructured":"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.  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."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089547989631442X"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0806020"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Hiriart-Urruty J.-B. and Lemarechal C. 1993. Convex Analysis and Minimization Algorithms Vol. 1 and 2. Springer.  Hiriart-Urruty J.-B. and Lemarechal C. 1993. Convex Analysis and Minimization Algorithms Vol. 1 and 2. Springer.","DOI":"10.1007\/978-3-662-02796-7_1"},{"key":"e_1_2_1_26_1","unstructured":"Hungerl\u00e4nder P. and Rendl F. 2011. Semidefinite relaxations of ordering problems. Math. Program. B. http:\/\/www.optimization-online.org\/DB_HTML\/2010\/08\/2696.html.  Hungerl\u00e4nder P. and Rendl F. 2011. Semidefinite relaxations of ordering problems. Math. Program. B. http:\/\/www.optimization-online.org\/DB_HTML\/2010\/08\/2696.html."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/647549.728900"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00001"},{"volume-title":"The Geometry of Metric and Linear Spaces","author":"Kelly J.","key":"e_1_2_1_29_1","unstructured":"Kelly , J. 1975. Hypermetric spaces . In The Geometry of Metric and Linear Spaces , L. Kelly, Ed., Lecture Notes in Mathematics. Springer , Berlin, 17--31. Kelly, J. 1975. Hypermetric spaces. In The Geometry of Metric and Linear Spaces, L. Kelly, Ed., Lecture Notes in Mathematics. Springer, Berlin, 17--31."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/0801013"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00397-9"},{"key":"e_1_2_1_32_1","first-page":"85","article-title":"On the bipartite crossing number","volume":"72","author":"May M.","year":"1988","unstructured":"May , M. and Szkatula , K. 1988 . On the bipartite crossing number . Control and Cybernetics 72 , 85 -- 97 . May, M. and Szkatula, K. 1988. On the bipartite crossing number. Control and Cybernetics 72, 85--97.","journal-title":"Control and Cybernetics"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-008-0235-8"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/647547.728617"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1981.4308636"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2133803.2330084","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2133803.2330084","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:05:52Z","timestamp":1750241152000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2133803.2330084"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":35,"alternative-id":["10.1145\/2133803.2330084"],"URL":"https:\/\/doi.org\/10.1145\/2133803.2330084","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}