{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,18]],"date-time":"2026-06-18T17:29:46Z","timestamp":1781803786871,"version":"3.54.5"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2019,7,19]],"date-time":"2019-07-19T00:00:00Z","timestamp":1563494400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["RU 1903\/3-1, WA 654\/21-1"],"award-info":[{"award-number":["RU 1903\/3-1, WA 654\/21-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2019,12,17]]},"abstract":"<jats:p>\n            In this article, we consider the\n            <jats:italic>rectilinear crossing minimization problem<\/jats:italic>\n            , i.e., we seek a straight-line drawing\u00a0\u0393 of a graph\n            <jats:italic>G<\/jats:italic>\n            =(\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            ) with a small number of edge crossings. Crossing minimization is an active field of research\u00a0[1, 10]. While there is a lot of work on heuristics for topological drawings, these techniques are typically not transferable to the rectilinear (i.e., straight-line) setting. We introduce and evaluate three heuristics for rectilinear crossing minimization. The approaches are based on the primitive operation of moving a single vertex to its crossing-minimal position in the current drawing \u0393, for which we give an\n            <jats:italic>O<\/jats:italic>\n            ((\n            <jats:italic>kn<\/jats:italic>\n            +\n            <jats:italic>m<\/jats:italic>\n            )\n            <jats:sup>2<\/jats:sup>\n            log (\n            <jats:italic>kn<\/jats:italic>\n            +\n            <jats:italic>m<\/jats:italic>\n            ))-time algorithm, where\n            <jats:italic>k<\/jats:italic>\n            is the degree of the vertex and\n            <jats:italic>n<\/jats:italic>\n            and\n            <jats:italic>m<\/jats:italic>\n            are the number of vertices and edges of the graph, respectively. In an experimental evaluation, we demonstrate that our algorithms compute straight-line drawings with fewer crossings than energy-based algorithms implemented in the O\n            <jats:sc>pen<\/jats:sc>\n            G\n            <jats:sc>raph<\/jats:sc>\n            D\n            <jats:sc>rawing<\/jats:sc>\n            F\n            <jats:sc>ramework<\/jats:sc>\n            \u00a0[11] on a varied set of benchmark instances. Additionally, we show that the difference of the number of crossings of topological drawings computed with the edge insertion approach\u00a0[10, 13] and the number of crossings in straight-line drawings computed by our heuristic is relatively small. All experiments are evaluated with a statistical significance level of \u03b1 = 0.05.\n          <\/jats:p>","DOI":"10.1145\/3325861","type":"journal-article","created":{"date-parts":[[2019,7,19]],"date-time":"2019-07-19T13:17:14Z","timestamp":1563542234000},"page":"1-21","source":"Crossref","is-referenced-by-count":5,"title":["Geometric Heuristics for Rectilinear Crossing Minimization"],"prefix":"10.1145","volume":"24","author":[{"given":"Marcel","family":"Radermacher","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Klara","family":"Reichard","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Passau, Passau, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ignaz","family":"Rutter","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Passau, Passau, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dorothea","family":"Wagner","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,7,19]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Thirty Essays on Geometric Graph Theory, J\u00e1nos Pach (Ed.)","author":"\u00c1brego Bernardo M.","unstructured":"Bernardo M. \u00c1brego , Silvia Fern\u00e1ndez-Merchant , and Gelasio Salazar . 2013. The rectilinear crossing number of K<sub>n<\/sub> : Closing in (or are we?) . In Thirty Essays on Geometric Graph Theory, J\u00e1nos Pach (Ed.) . Springer New York , 5--18. Bernardo M. \u00c1brego, Silvia Fern\u00e1ndez-Merchant, and Gelasio Salazar. 2013. The rectilinear crossing number of K<sub>n<\/sub> : Closing in (or are we?). In Thirty Essays on Geometric Graph Theory, J\u00e1nos Pach (Ed.). Springer New York, 5--18."},{"key":"e_1_2_1_2_1","unstructured":"Oswin Aichholzer. 2017. On the Rectilinear Crossing Number. Retrieved from: http:\/\/www.ist.tugraz.at\/staff\/aichholzer\/research\/rp\/triangulations\/crossing.  Oswin Aichholzer. 2017. On the Rectilinear Crossing Number. Retrieved from: http:\/\/www.ist.tugraz.at\/staff\/aichholzer\/research\/rp\/triangulations\/crossing."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1979.1675432"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00042-9"},{"key":"e_1_2_1_5_1","first-page":"443","article-title":"Some provably hard crossing number problems. Disc. 8","volume":"6","author":"Bienstock Daniel","year":"1991","unstructured":"Daniel Bienstock . 1991 . Some provably hard crossing number problems. Disc. 8 Comput. Geo. 6 , 1 (1991), 443 -- 459 . Daniel Bienstock. 1991. Some provably hard crossing number problems. Disc. 8 Comput. Geo. 6, 1 (1991), 443--459.","journal-title":"Comput. Geo."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190170308"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-51963-0_23"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1758612.1758620"},{"key":"e_1_2_1_9_1","first-page":"323","article-title":"Fast generation of planar graphs","volume":"58","author":"Brinkmann Gunnar","year":"2007","unstructured":"Gunnar Brinkmann and Brendan D. McKay . 2007 . Fast generation of planar graphs . MATCH-Commun. Math. Comput. Chem. 58 , 2 (2007), 323 -- 357 . Gunnar Brinkmann and Brendan D. McKay. 2007. Fast generation of planar graphs. MATCH-Commun. Math. Comput. Chem. 58, 2 (2007), 323--357.","journal-title":"MATCH-Commun. Math. Comput. Chem."},{"key":"e_1_2_1_10_1","first-page":"43","article-title":"Crossings and planarization. In Handbook of Graph Drawing and Visualization, Roberto Tamassia (Ed.). Chapman and Hall\/CRC","volume":"2","author":"Buchheim Christoph","year":"2013","unstructured":"Christoph Buchheim , Markus Chimani , Carsten Gutwenger , Michael J\u00fcnger , and Petra Mutzel . 2013 . Crossings and planarization. In Handbook of Graph Drawing and Visualization, Roberto Tamassia (Ed.). Chapman and Hall\/CRC , Chapter 2 , 43 -- 85 . Christoph Buchheim, Markus Chimani, Carsten Gutwenger, Michael J\u00fcnger, and Petra Mutzel. 2013. Crossings and planarization. In Handbook of Graph Drawing and Visualization, Roberto Tamassia (Ed.). Chapman and Hall\/CRC, Chapter 2, 43--85.","journal-title":"Chapter"},{"key":"e_1_2_1_11_1","first-page":"543","article-title":"The open graph drawing framework (OGDF). In Handbook of Graph Drawing and Visualization, Roberto Tamassia (Ed.). Chapman and Hall\/CRC","volume":"17","author":"Chimani Markus","year":"2013","unstructured":"Markus Chimani , Carsten Gutwenger , Michael J\u00fcnger , Gunnar W. Klau , Karsten Klein , and Petra Mutzel . 2013 . The open graph drawing framework (OGDF). In Handbook of Graph Drawing and Visualization, Roberto Tamassia (Ed.). Chapman and Hall\/CRC , Chapter 17 , 543 -- 569 . Markus Chimani, Carsten Gutwenger, Michael J\u00fcnger, Gunnar W. Klau, Karsten Klein, and Petra Mutzel. 2013. The open graph drawing framework (OGDF). In Handbook of Graph Drawing and Visualization, Roberto Tamassia (Ed.). Chapman and Hall\/CRC, Chapter 17, 543--569.","journal-title":"Chapter"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 17th International Symposium on Experimental Algorithms (SEA\u201918) (Leibniz International Proceedings in Informatics (LIPIcs)), Gianlorenzo D\u2019Angelo (Ed.)","volume":"103","author":"Chimani Markus","year":"2018","unstructured":"Markus Chimani , Ivo Hedtke , and Tilo Wiedera . 2018 . Exact algorithms for the maximum planar subgraph problem: New models and experiments . In Proceedings of the 17th International Symposium on Experimental Algorithms (SEA\u201918) (Leibniz International Proceedings in Informatics (LIPIcs)), Gianlorenzo D\u2019Angelo (Ed.) , Vol. 103 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 22:1--22:15. Markus Chimani, Ivo Hedtke, and Tilo Wiedera. 2018. Exact algorithms for the maximum planar subgraph problem: New models and experiments. In Proceedings of the 17th International Symposium on Experimental Algorithms (SEA\u201918) (Leibniz International Proceedings in Informatics (LIPIcs)), Gianlorenzo D\u2019Angelo (Ed.), Vol. 103. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 22:1--22:15."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 32nd Symposium on Computational Geometry (SoCG\u201916) (Leibniz International Proceedings in Informatics (LIPIcs)), S\u00e1ndor Fekete and Anna Lubiw (Eds.)","volume":"51","author":"Chimani Markus","year":"2016","unstructured":"Markus Chimani and Petr Hlinen\u00fd . 2016 . Inserting multiple edges into a planar graph . In Proceedings of the 32nd Symposium on Computational Geometry (SoCG\u201916) (Leibniz International Proceedings in Informatics (LIPIcs)), S\u00e1ndor Fekete and Anna Lubiw (Eds.) , Vol. 51 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 30:1--30:15. Markus Chimani and Petr Hlinen\u00fd. 2016. Inserting multiple edges into a planar graph. In Proceedings of the 32nd Symposium on Computational Geometry (SoCG\u201916) (Leibniz International Proceedings in Informatics (LIPIcs)), S\u00e1ndor Fekete and Anna Lubiw (Eds.), Vol. 51. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 30:1--30:15."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/234535.234538"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00328"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-50106-2_32"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/647546.730941"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380211102"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31843-9_25"},{"key":"e_1_2_1_20_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman . Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0604033"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1128-8"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31843-9_29"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.709399"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90102-6"},{"key":"e_1_2_1_26_1","volume-title":"Handbook of Graph Drawing and Visualization","author":"Kobourov Stephen G.","unstructured":"Stephen G. Kobourov . 2013. Force-directed drawing algorithms . In Handbook of Graph Drawing and Visualization , Roberto Tamassia (Ed.). Chapman and Hall\/CRC , Chapter 12. Stephen G. Kobourov. 2013. Force-directed drawing algorithms. In Handbook of Graph Drawing and Visualization, Roberto Tamassia (Ed.). Chapman and Hall\/CRC, Chapter 12."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208049"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.78.046110"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90060-4"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/647547.728624"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975055.12"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11805-0_32"},{"key":"e_1_2_1_33_1","volume-title":"Handbook of Parametric and Nonparametric Statistical Procedures","author":"Sheskin David J.","unstructured":"David J. Sheskin . 2003. Handbook of Parametric and Nonparametric Statistical Procedures . Chapman and Hall\/CRC. David J. Sheskin. 2003. Handbook of Parametric and Nonparametric Statistical Procedures. Chapman and Hall\/CRC."},{"key":"e_1_2_1_34_1","volume-title":"Stretchability of pseudolines is NP-hard","author":"Shor Peter W.","unstructured":"Peter W. Shor . 1991. Stretchability of pseudolines is NP-hard . In Applied Geometry and Discrete Mathematics\u2014The Victor Klee Festschrift, Bernd Sturmfels and Peter Gritzmann (Eds.). Vol. 4 . AMS, DIMACS , and ACM , 531--554. Peter W. Shor. 1991. Stretchability of pseudolines is NP-hard. In Applied Geometry and Discrete Mathematics\u2014The Victor Klee Festschrift, Bernd Sturmfels and Peter Gritzmann (Eds.). Vol. 4. AMS, DIMACS, and ACM, 531--554."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1017\/nws.2016.20"},{"key":"e_1_2_1_36_1","volume-title":"CGAL User and Reference Manual","author":"Project The CGAL","unstructured":"The CGAL Project . 2017. CGAL User and Reference Manual . CGAL editorial board. Retrieved from: http:\/\/doc.cgal.org\/4.10\/Manual\/packages.html. The CGAL Project. 2017. CGAL User and Reference Manual. CGAL editorial board. Retrieved from: http:\/\/doc.cgal.org\/4.10\/Manual\/packages.html."},{"key":"e_1_2_1_37_1","unstructured":"Imrich Vrt\u2019o. 2014. Bibliography on Crossing Numbers of Graphs. Retrieved from: ftp:\/\/ftp.ifi.savba.sk\/pub\/imrich\/crobib.pdf.  Imrich Vrt\u2019o. 2014. Bibliography on Crossing Numbers of Graphs. Retrieved from: ftp:\/\/ftp.ifi.savba.sk\/pub\/imrich\/crobib.pdf."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3325861","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3325861","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:08Z","timestamp":1750204388000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3325861"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,19]]},"references-count":37,"alternative-id":["10.1145\/3325861"],"URL":"https:\/\/doi.org\/10.1145\/3325861","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,19]]}}}