{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,18]],"date-time":"2026-06-18T17:29:59Z","timestamp":1781803799177,"version":"3.54.5"},"reference-count":52,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2019,11,29]],"date-time":"2019-11-29T00:00:00Z","timestamp":1574985600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001659","name":"DFG","doi-asserted-by":"publisher","award":["Ka812\/17-1"],"award-info":[{"award-number":["Ka812\/17-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,1,19]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>The crossing resolution of a non-planar drawing of a graph is the value of the minimum angle formed by any pair of crossing edges. Recent experiments suggest that the larger the crossing resolution is, the easier it is to read and interpret a drawing of a graph. However, maximizing the crossing resolution turns out to be an NP-hard problem in general, and only heuristic algorithms are known that are mainly based on appropriately adjusting force-directed algorithms. In this paper, we propose a new heuristic algorithm for the crossing resolution maximization problem and we experimentally compare it against the known approaches from the literature. Our experimental evaluation indicates that the new heuristic produces drawings with better crossing resolution, but this comes at the cost of slightly higher edge-length ratio, especially when the input graph is large.<\/jats:p>","DOI":"10.1093\/comjnl\/bxz133","type":"journal-article","created":{"date-parts":[[2019,10,2]],"date-time":"2019-10-02T19:36:29Z","timestamp":1570044989000},"page":"7-26","source":"Crossref","is-referenced-by-count":7,"title":["A Heuristic Approach Towards Drawings of Graphs With High Crossing Resolution"],"prefix":"10.1093","volume":"64","author":[{"given":"Michael A","family":"Bekos","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t T\u00fcbingen, T\u00fcbingen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Henry","family":"F\u00f6rster","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t T\u00fcbingen, T\u00fcbingen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian","family":"Geckeler","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t T\u00fcbingen, T\u00fcbingen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lukas","family":"Holl\u00e4nder","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t T\u00fcbingen, T\u00fcbingen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Kaufmann","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t T\u00fcbingen, T\u00fcbingen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amad\u00e4us M","family":"Spallek","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t T\u00fcbingen, T\u00fcbingen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Splett","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t T\u00fcbingen, T\u00fcbingen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2019,11,29]]},"reference":[{"key":"2021011807350335800_ref1","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF02122694","article-title":"How to draw a planar graph on a grid","volume":"10","author":"de Fraysseix","year":"1990","journal-title":"Combinatorica"},{"key":"2021011807350335800_ref2","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/3-540-37623-2_13","article-title":"Planar polyline drawings with good angular resolution","volume-title":"Graph Drawing, Montr\u00e9al, Canada","author":"Gutwenger","year":"1998"},{"key":"2021011807350335800_ref3","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1007\/BF02086606","article-title":"Drawing planar graphs using the canonical ordering","volume":"16","author":"Kant","year":"1996","journal-title":"Algorithmica"},{"key":"2021011807350335800_ref4","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/S0953-5438(00)00032-1","article-title":"Effective information visualisation: a study of graph drawing aesthetics and algorithms","volume":"13","author":"Purchase","year":"2000","journal-title":"Interact. Comput."},{"key":"2021011807350335800_ref5","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/BF01187020","article-title":"Edge crossings in drawings of bipartite graphs","volume":"11","author":"Eades","year":"1994","journal-title":"Algorithmica"},{"key":"2021011807350335800_ref6","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1109\/TSMC.1981.4308636","article-title":"Methods for visual understanding of hierarchical system structures","volume":"11","author":"Sugiyama","year":"1981","journal-title":"IEEE Trans. Syst. Man Cybern."},{"key":"2021011807350335800_ref7","first-page":"149","article-title":"A heuristic for graph drawing","volume":"42","author":"Eades","year":"1984","journal-title":"Congressus Numerantium"},{"key":"2021011807350335800_ref8","doi-asserted-by":"crossref","first-page":"1129","DOI":"10.1002\/spe.4380211102","article-title":"Graph drawing by force-directed placement","volume":"21","author":"Fruchterman","year":"1991","journal-title":"Softw. Pract. Exper."},{"key":"2021011807350335800_ref9","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"Di Battista","year":"1999"},{"key":"2021011807350335800_ref10","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-44969-8","volume-title":"Drawing Graphs, Methods and Models","author":"Kaufmann","year":"2001"},{"key":"2021011807350335800_ref11","doi-asserted-by":"crossref","DOI":"10.1201\/b15385","volume-title":"Handbook on Graph Drawing and Visualization","author":"Tamassia","year":"2013"},{"key":"2021011807350335800_ref12","doi-asserted-by":"crossref","DOI":"10.1109\/APVIS.2007.329282","article-title":"Using eye tracking to investigate graph layout effects","volume-title":"APVIS","author":"Huang","year":"2007"},{"key":"2021011807350335800_ref13","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1016\/j.jvlc.2014.03.001","article-title":"Larger crossing angles make graphs easier to read","volume":"25","author":"Huang","year":"2014","journal-title":"J. Vis. Lang. Comput."},{"key":"2021011807350335800_ref14","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1007\/3-540-63938-1_67","article-title":"Which aesthetic has the greatest effect on human understanding?","volume-title":"Graph Drawing, Rome, Italy","author":"Purchase","year":"1997"},{"key":"2021011807350335800_ref15","article-title":"Algorithmics for beyond planar graphs","volume":"089","author":"Hong","year":"2016","journal-title":"NII Shonan Meeting Seminar"},{"key":"2021011807350335800_ref16","article-title":"Beyond planar graphs: algorithmics and combinatorics","volume":"16452","author":"Kaufmann","year":"2016","journal-title":"Dagstuhl Seminar"},{"key":"2021011807350335800_ref17","article-title":"Graph drawing beyond planarity: some results and open problems","author":"Liotta","year":"2017"},{"key":"2021011807350335800_ref18","article-title":"A survey on graph drawing beyond planarity","author":"Didimo","year":"2018"},{"key":"2021011807350335800_ref19","doi-asserted-by":"crossref","first-page":"5156","DOI":"10.1016\/j.tcs.2011.05.025","article-title":"Drawing graphs with right angle crossings","volume":"412","author":"Didimo","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"2021011807350335800_ref20","doi-asserted-by":"crossref","first-page":"569","DOI":"10.7155\/jgaa.00274","article-title":"The straight-line RAC drawing problem is NP-hard","volume":"16","author":"Argyriou","year":"2012","journal-title":"J. Graph Algorithms Appl."},{"key":"2021011807350335800_ref21","doi-asserted-by":"crossref","first-page":"887","DOI":"10.1093\/comjnl\/bxs088","article-title":"Maximizing the total resolution of graphs","volume":"56","author":"Argyriou","year":"2013","journal-title":"Comput. J."},{"key":"2021011807350335800_ref22","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1016\/j.jvlc.2011.12.002","article-title":"Improving multiple aesthetics produces better graph drawings","volume":"24","author":"Huang","year":"2013","journal-title":"J. Vis. Lang. Comput."},{"key":"2021011807350335800_ref23","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-51963-0_23","article-title":"How to draw a planarization","volume-title":"SOFSEM, Limerick, Ireland","author":"Bl\u00e4sius","year":"2017"},{"key":"2021011807350335800_ref24","article-title":"A linear-time heuristic for improving network partitions","volume-title":"Design Automation Conference, DAC, Las Vegas, NV","author":"Fiduccia","year":"1982"},{"key":"2021011807350335800_ref25","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1002\/j.1538-7305.1970.tb01770.x","article-title":"An efficient heuristic procedure for partitioning graphs","volume":"49","author":"Kernighan","year":"1970","journal-title":"Bell Syst. Tech. J."},{"key":"2021011807350335800_ref26","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611975055.12","article-title":"A geometric heuristic for rectilinear crossing minimization","volume-title":"Workshop on Algorithm Engineering and Experiments ALENEX, New Orleans, LA, USA","author":"Radermacher","year":"2018"},{"key":"2021011807350335800_ref27","doi-asserted-by":"crossref","DOI":"10.1145\/2433396.2433461","article-title":"Balanced label propagation for partitioning massive graphs","volume-title":"ACM Int. Conf. on Web Search and Data Mining, Rome Italy","author":"Ugander","year":"2013"},{"key":"2021011807350335800_ref28","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1002\/net.3230240203","article-title":"An efficient graph planarization two-phase heuristic","volume":"24","author":"Goldschmidt","year":"1994","journal-title":"Networks"},{"key":"2021011807350335800_ref29","doi-asserted-by":"crossref","first-page":"1035","DOI":"10.1137\/0222063","article-title":"Drawing graphs in the plane with high resolution","volume":"22","author":"Formann","year":"1993","journal-title":"SIAM J. Comput."},{"key":"2021011807350335800_ref30","doi-asserted-by":"crossref","first-page":"961","DOI":"10.1016\/j.dam.2012.11.019","article-title":"Right angle crossing graphs and 1-planarity","volume":"161","author":"Eades","year":"2013","journal-title":"Discrete Appl. Math."},{"key":"2021011807350335800_ref31","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.dam.2017.08.015","article-title":"Nic-planar graphs","volume":"232","author":"Bachmaier","year":"2017","journal-title":"Discrete Appl. Math."},{"key":"2021011807350335800_ref32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2016.04.026","article-title":"Recognizing and drawing ic-planar graphs","volume":"636","author":"Brandenburg","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"2021011807350335800_ref33","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1016\/j.tcs.2017.05.039","article-title":"On RAC drawings of 1-planar graphs","volume":"689","author":"Bekos","year":"2017","journal-title":"Theor. Comput. Sci."},{"key":"2021011807350335800_ref34","doi-asserted-by":"crossref","first-page":"53","DOI":"10.7155\/jgaa.00217","article-title":"On the perspectives opened by right angle crossing drawings","volume":"15","author":"Angelini","year":"2011","journal-title":"J. Graph Algorithms Appl."},{"key":"2021011807350335800_ref35","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/j.comgeo.2011.11.008","article-title":"Graphs that admit right angle crossing drawings","volume":"45","author":"Arikushi","year":"2012","journal-title":"Comput. Geom."},{"key":"2021011807350335800_ref36","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1007\/s00224-010-9275-6","article-title":"Area, curve complexity, and crossing resolution of non-planar graph drawings","volume":"49","author":"Di Giacomo","year":"2011","journal-title":"Theory Comput. Syst."},{"key":"2021011807350335800_ref37","first-page":"200","article-title":"Large angle crossing drawings of planar graphs in subquadratic area","volume-title":"EGC,Alcal\u00e1 de Henares, Spain","author":"Angelini","year":"2011"},{"key":"2021011807350335800_ref38","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1016\/j.ipl.2010.05.023","article-title":"A characterization of complete bipartite RAC graphs","volume":"110","author":"Didimo","year":"2010","journal-title":"Inf. Process. Lett."},{"key":"2021011807350335800_ref39","doi-asserted-by":"crossref","first-page":"954","DOI":"10.1007\/s00453-012-9706-7","article-title":"2-layer right angle crossing drawings","volume":"68","author":"Di Giacomo","year":"2014","journal-title":"Algorithmica"},{"key":"2021011807350335800_ref40","first-page":"406","article-title":"Testing full outer-2-planarity in linear time","volume-title":"WG, Garching, Germany","author":"Hong","year":"2015"},{"key":"2021011807350335800_ref41","article-title":"Notes on large angle crossing graphs","volume":"2011","author":"Dujmovic","year":"2011","journal-title":"Chicago J. Theor. Comput. Sci."},{"key":"2021011807350335800_ref42","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/100819564","article-title":"Graphs that admit polyline drawings with few crossing angles","volume":"26","author":"Ackerman","year":"2012","journal-title":"SIAM J. Discrete Math."},{"key":"2021011807350335800_ref43","author":"Didimo","year":"2010"},{"key":"2021011807350335800_ref44","first-page":"165","article-title":"Topology-driven force-directed algorithms","volume-title":"Graph Drawing, Konstanz, Germany","author":"Didimo","year":"2010"},{"key":"2021011807350335800_ref45","first-page":"397","article-title":"Large crossing angles in circular layouts","volume-title":"Graph Drawing, Konstanz, Germany","author":"Nguyen","year":"2010"},{"key":"2021011807350335800_ref46","article-title":"Graph drawing contest report","volume-title":"Graph Drawing and Network Visualization, Boston, MA, USA","author":"Devanny","year":"2017"},{"key":"2021011807350335800_ref47","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-030-04414-5_20","article-title":"A greedy heuristic for crossing-angle maximization","volume-title":"Graph Drawing and Network Visualization, Barcelona, Spain, Cham, 26-28 September, LNCS, 11282, pp. 286\u2013299","author":"Demel","year":"2018"},{"key":"2021011807350335800_ref48","article-title":"Graph drawing contest report","volume-title":"Graph Drawing and Network Visualization, Barcelona, Spain","author":"Devanny","year":"2018"},{"key":"2021011807350335800_ref49","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational geometry: algorithms and applications","author":"de Berg","year":"2008"},{"key":"2021011807350335800_ref50","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/j.tcs.2018.10.002","article-title":"On the edge-length ratio of outerplanar graphs","volume":"770","author":"Lazard","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"2021011807350335800_ref51","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-18638-7_8","article-title":"yFiles\u2014visualization and automatic layout of graphs","volume-title":"Graph Drawing Software","author":"Wiese","year":"2004"},{"key":"2021011807350335800_ref52","first-page":"571","article-title":"Gdtoolkit","volume-title":"Handbook on Graph Drawing and Visualization","author":"Di Battista","year":"2013"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/64\/1\/7\/35886363\/bxz133.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/64\/1\/7\/35886363\/bxz133.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,18]],"date-time":"2021-01-18T14:00:14Z","timestamp":1610978414000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/64\/1\/7\/5645631"}},"subtitle":[],"editor":[{"given":"Iain","family":"Stewart","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2019,11,29]]},"references-count":52,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2019,11,29]]},"published-print":{"date-parts":[[2021,1,19]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxz133","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,1]]},"published":{"date-parts":[[2019,11,29]]}}}