{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,3]],"date-time":"2024-05-03T11:49:34Z","timestamp":1714736974749},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","funder":[{"name":"priority project","award":["1307"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2010,3]]},"abstract":"\n An upward drawing of a DAG\n G<\/jats:italic>\n is a drawing of\n G<\/jats:italic>\n in which all arcs are drawn as curves increasing monotonically in the vertical direction. In this article, we present a new approach for upward crossing minimization, that is, finding an upward drawing of a DAG\n G<\/jats:italic>\n with as few crossings as possible. Our algorithm is based on a two-stage upward planarization approach, which computes a feasible upward planar subgraph in the first step and reinserts the remaining arcs by computing constraint-feasible upward insertion paths. An experimental study shows that the new algorithm leads to much better results than existing algorithms for upward crossing minimization, including the classical Sugiyama approach.\n <\/jats:p>","DOI":"10.1145\/1671970.1671975","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":11,"title":["Layer-free upward crossing minimization"],"prefix":"10.1145","volume":"15","author":[{"given":"Markus","family":"Chimani","sequence":"first","affiliation":[{"name":"TU Dortmund, Dortmund, Germany"}]},{"given":"Carsten","family":"Gutwenger","sequence":"additional","affiliation":[{"name":"TU Dortmund, Dortmund, Germany"}]},{"given":"Petra","family":"Mutzel","sequence":"additional","affiliation":[{"name":"TU Dortmund, Dortmund, Germany"}]},{"given":"Hoi-Ming","family":"Wong","sequence":"additional","affiliation":[{"name":"TU Dortmund, Dortmund, Germany"}]}],"member":"320","published-online":{"date-parts":[[2010,3,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0164-1212(84)90006-2"},{"key":"e_1_2_1_2_1","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"Battista G. D.","year":"1999","unstructured":"Battista , G. D. , Eades , P. , Tamassia , R. , and Tollis , I. G . 1999 . Graph Drawing: Algorithms for the Visualization of Graphs . Prentice-Hall , Upper Saddle River, NJ. Battista, G. D., Eades, P., Tamassia, R., and Tollis, I. G. 1999. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, Upper Saddle River, NJ."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01188716"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794279626"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195900000358"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(96)00005-3"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the Symposium on Graph Drawing. Springer","author":"Dogrusoz U.","unstructured":"Dogrusoz , U. , Duncan , C. A. , Gutwenger , C. , and Sander , G . 2008. Graph drawing contest report . In Proceedings of the Symposium on Graph Drawing. Springer , Berlin. Dogrusoz, U., Duncan, C. A., Gutwenger, C., and Sander, G. 2008. Graph drawing contest report. In Proceedings of the Symposium on Graph Drawing. Springer, Berlin."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00067"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31843-9_17"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.221135"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794277123"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230240203"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the Symposium on Graph Drawing. Springer","author":"Gutwenger C.","unstructured":"Gutwenger , C. and Mutzel , P . 2004. An experimental study of crossing minimization heuristics . In Proceedings of the Symposium on Graph Drawing. Springer , Berlin, 13--24. Gutwenger, C. and Mutzel, P. 2004. An experimental study of crossing minimization heuristics. In Proceedings of the Symposium on Graph Drawing. Springer, Berlin, 13--24."},{"key":"e_1_2_1_14_1","volume-title":"Chair of Algorithm Engineering","author":"Open TU","year":"2007","unstructured":"OGDF. Open graph drawing framework. TU Dortmund , Chair of Algorithm Engineering ; Version v. 2007 .11 (Bubinga) . http:\/\/www.ogdf.net. OGDF. Open graph drawing framework. TU Dortmund, Chair of Algorithm Engineering; Version v.2007.11 (Bubinga). http:\/\/www.ogdf.net."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11618058_52"},{"key":"e_1_2_1_16_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\/pdf\/10.1145\/1671970.1671975","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T06:38:27Z","timestamp":1672295907000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1671970.1671975"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3]]},"references-count":16,"alternative-id":["10.1145\/1671970.1671975"],"URL":"https:\/\/doi.org\/10.1145\/1671970.1671975","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,3]]}}}