{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,4]],"date-time":"2023-01-04T06:05:19Z","timestamp":1672812319853},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2001,12,31]]},"abstract":"\n We consider the one-sided crossing minimization problem (CP):\ngiven a bipartite graph\n G<\/jats:italic>\n and a permutation\n \n x\n 0<\/jats:sub>\n <\/jats:italic>\n of the vertices on a layer, find a perumuation\n \n x\n 1<\/jats:sub>\n <\/jats:italic>\n of the vertices on the other layer which\nminimizes the number of edge crossings in any straightline drawing\nof\n G<\/jats:italic>\n where vertices are placed on two parallel lines and\nsorted according to\n \n x\n 0<\/jats:sub>\n <\/jats:italic>\n and\n \n x\n 1<\/jats:sub>\n <\/jats:italic>\n .\nSolving CP represents a fundamental step in the construction of\naesthetically pleasing layouts of heirarchies and directed graphs,\nbut unfortunately this problem has been proved to be\nNP-complete.\n <\/jats:p>\n In this paper we address the strong relation between CP and the\nproblem of computing minimum feedback arc sets in directed graphs\nand we devise a enw approximation algorithm for CP, called PM, that\nexploits this dependency. We experimantally and visually compare\nthe performance of PM with the performance of well-known algorithms\nand of recent attractive strategies. Experiments are carried out on\ndifferent families of randomly generated graphs, on pathological\ninstances, and on real test sets. Performance indicators include\nboth number of edge crossings and running time, as well as\nstructural measures of the problem instances. We found CP to be a\nvery interesting and rich problem from a combinatorial point of\nview. Our results clearly separate the behavior of the algorithms,\nproving the effectiveness of PM on most test sets and showing\ntradeoffs between quality of the solutions and running time.\nHowever, if the visual complexity of the drawings is considered, we\nfound no clear winner. This confirms the importance of optimizing\nalso other aesthetic criteria such as symmetry, edge length, and\nangular resolution.<\/jats:p>","DOI":"10.1145\/945394.945396","type":"journal-article","created":{"date-parts":[[2005,8,2]],"date-time":"2005-08-02T06:34:09Z","timestamp":1122964449000},"page":"2","source":"Crossref","is-referenced-by-count":7,"title":["Breaking cycles for minimizing crossings"],"prefix":"10.1145","volume":"6","author":[{"given":"Camil","family":"Demestrescu","sequence":"first","affiliation":[{"name":"Universit\u00e1 di Roma \"La Sapienza\""}]},{"given":"Irene","family":"Finocchi","sequence":"additional","affiliation":[{"name":"Universit\u00e1 di Roma \"La Sapienza\""}]}],"member":"320","published-online":{"date-parts":[[2001,12,31]]},"reference":[{"key":"e_1_2_1_1_2","volume-title":"Approximate Solution of NP-Hard Optimization Problems","author":"Ausiello G.","year":"1999","unstructured":"G. Ausiello , P. Crescenzi , G. Gambosi , V. Kann , A. Marchetti-Spaccamela , and M. Protasi . Approximate Solution of NP-Hard Optimization Problems . Springer Verlag , 1999 .]] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi.Approximate Solution of NP-Hard Optimization Problems. Springer Verlag, 1999.]]"},{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/646687.702951"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.5555\/265834.265854"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1980.4308390"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/21.364865"},{"key":"e_1_2_1_6_2","volume-title":"Introduction to Algorithms","author":"Cormen T.H.","year":"2001","unstructured":"T.H. Cormen , C.E. Leiserson , R.L. Rivest , and C. Stein . Introduction to Algorithms . McGraw-Hill , 2001 .]] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein. Introduction to Algorithms.McGraw-Hill, 2001.]]"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1006\/jvlc.1999.0143"},{"key":"e_1_2_1_8_2","unstructured":"C. Demetrescu and I. Finocchi. Leonardo's repository of animated algorithms. Available athttp:\/\/www.dis.uniroma1.it\/~demetres\/Leonardo\/ProgramsRepository.html.]] C. Demetrescu and I. Finocchi. Leonardo's repository of animated algorithms. Available athttp:\/\/www.dis.uniroma1.it\/~demetres\/Leonardo\/ProgramsRepository.html.]]"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00491-X"},{"key":"e_1_2_1_10_2","first-page":"171","volume-title":"Proc. of the 2nd International Workshop onAlgorithm Engineering and Experiments (ALENEX'00)","author":"Demetrescu C.","year":"2000","unstructured":"C. Demetrescu and I. Finocchi . Break the \"right\" cycles and get the \"best\" drawing. InB.E. Moret and A.V. Goldberg, editors , Proc. of the 2nd International Workshop onAlgorithm Engineering and Experiments (ALENEX'00) , pages 171 - 182 , 2000 .]] C. Demetrescu and I. Finocchi. Break the \"right\" cycles and get the \"best\" drawing. InB.E. Moret and A.V. Goldberg, editors, Proc. of the 2nd International Workshop onAlgorithm Engineering and Experiments (ALENEX'00), pages 171-182, 2000.]]"},{"key":"e_1_2_1_11_2","volume-title":"Graph Drawing: Algorithms for theVisualization of Graphs","author":"Di Battista G.","year":"1999","unstructured":"G. Di Battista , P. Eades , R. Tamassia , and I. Tollis . Graph Drawing: Algorithms for theVisualization of Graphs . Prentice Hall , Upper Saddle River, NJ, 1999 .]] G. Di Battista, P. Eades, R. Tamassia, and I. Tollis. Graph Drawing: Algorithms for theVisualization of Graphs. Prentice Hall, Upper Saddle River, NJ, 1999.]]"},{"key":"e_1_2_1_12_2","first-page":"121","volume-title":"A new heuristic layout algorithm for dags","author":"Dresbach S.","year":"1994","unstructured":"S. Dresbach . A new heuristic layout algorithm for dags . In U. Derigs and A. Drexl, editors,Operations Research Proceedings , pages 121 - 126 , 1994 .]] S. Dresbach. A new heuristic layout algorithm for dags. In U. Derigs and A. Drexl, editors,Operations Research Proceedings, pages 121-126, 1994.]]"},{"key":"e_1_2_1_13_2","first-page":"89","article-title":"Heuristics for reducing crossings in 2-layered networks","volume":"21","author":"Eades P.","year":"1986","unstructured":"P. Eades and D. Kelly . Heuristics for reducing crossings in 2-layered networks . Ars Combin. , 21 : 89 - 98 , 1986 .]] P. Eades and D. Kelly. Heuristics for reducing crossings in 2-layered networks. Ars Combin.,21:89-98, 1986.]]","journal-title":"Ars Combin."},{"key":"e_1_2_1_14_2","first-page":"15","article-title":"A new heuristic for the feedback arc set problem","volume":"12","author":"Eades P.","year":"1995","unstructured":"P. Eades and X. Lin . A new heuristic for the feedback arc set problem . Australian Journalof Combinatorics , 12 : 15 - 26 , 1995 .]] P. Eades and X. Lin. A new heuristic for the feedback arc set problem. Australian Journalof Combinatorics, 12:15-26, 1995.]]","journal-title":"Australian Journalof Combinatorics"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90079-O"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90179-1"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187020"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796281"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.221135"},{"key":"e_1_2_1_20_2","volume-title":"Computers and Intractability: a Guide to Theory of NP-completeness","author":"Garey M.R..","year":"1979","unstructured":"M.R.. Garey and D.S. Johnson . Computers and Intractability: a Guide to Theory of NP-completeness . W.H.Freeman , 1979 .]] M.R.. Garey and D.S. Johnson. Computers and Intractability: a Guide to Theory of NP-completeness. W.H.Freeman, 1979.]]"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.5555\/647256.760172"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00001"},{"key":"e_1_2_1_23_2","volume-title":"The Stanford GraphBase: A platform for combinatorial computing","author":"Knuth D.E.","year":"1993","unstructured":"D.E. Knuth . The Stanford GraphBase: A platform for combinatorial computing . Addison-Wesley , 1993 .]] D.E. Knuth. The Stanford GraphBase: A platform for combinatorial computing. Addison-Wesley, 1993.]]"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46648-7_22"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.5555\/647550.729096"},{"key":"e_1_2_1_27_2","unstructured":"S. North. 5114 directed graphs. Available at ftp:\/\/ftp.research.att.com\/dist\/drawdag\/ 1995.]] S. North. 5114 directed graphs. Available at ftp:\/\/ftp.research.att.com\/dist\/drawdag\/ 1995.]]"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/264216.264222"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.5555\/259794.259802"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200760"},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1981.4308636"},{"key":"e_1_2_1_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(95)00356-8"},{"key":"e_1_2_1_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1977.4309760"},{"key":"e_1_2_1_34_2","doi-asserted-by":"publisher","DOI":"10.5555\/1765751.1765764"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/945394.945396","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,3]],"date-time":"2023-01-03T07:24:36Z","timestamp":1672730676000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/945394.945396"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,12,31]]},"references-count":33,"alternative-id":["10.1145\/945394.945396"],"URL":"http:\/\/dx.doi.org\/10.1145\/945394.945396","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":["Theoretical Computer Science"],"published":{"date-parts":[[2001,12,31]]}}}