{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,8]],"date-time":"2024-01-08T12:39:59Z","timestamp":1704717599451},"reference-count":17,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2018,6]]},"abstract":"<jats:p> We introduce L-drawings, a novel paradigm for representing directed graphs aiming at combining the readability features of orthogonal drawings with the expressive power of adjacency matrix representations. In an L-drawing, vertices have exclusive [Formula: see text]- and [Formula: see text]-coordinates and edges consist of two segments, one exiting the source vertically and one entering the destination horizontally. <\/jats:p><jats:p> We study the problem of computing L-drawings using minimum ink. We prove its NP-hardness and provide a heuristic based on a polynomial-time algorithm that adds a vertex to a drawing using the minimum additional ink. We performed an experimental analysis of the heuristic which confirms its effectiveness. <\/jats:p>","DOI":"10.1142\/s0129054118410010","type":"journal-article","created":{"date-parts":[[2018,6,29]],"date-time":"2018-06-29T03:14:49Z","timestamp":1530242089000},"page":"461-480","source":"Crossref","is-referenced-by-count":4,"title":["Algorithms and Bounds for L-Drawings of Directed Graphs"],"prefix":"10.1142","volume":"29","author":[{"given":"Patrizio","family":"Angelini","sequence":"first","affiliation":[{"name":"Wilhelm-Schickard-Institut f\u00fcr Informatik, Universit\u00e4t T\u00fcbingen, Sand 14, 72076, T\u00fcbingen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giordano Da","family":"Lozzo","sequence":"additional","affiliation":[{"name":"Computer Science Department, University of California, Irvine, Donald Bren School of Information and Computer Sciences, Irvine, 92697-3435, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco Di","family":"Bartolomeo","sequence":"additional","affiliation":[{"name":"Department of Engineering, Roma Tre University, Via Della Vasca Navale 79, 00146, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Valentino Di","family":"Donato","sequence":"additional","affiliation":[{"name":"Department of Engineering, Roma Tre University, Via Della Vasca Navale 79, 00146, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maurizio","family":"Patrignani","sequence":"additional","affiliation":[{"name":"Department of Engineering, Roma Tre University, Via Della Vasca Navale 79, 00146, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincenzo","family":"Roselli","sequence":"additional","affiliation":[{"name":"Department of Engineering, Roma Tre University, Via Della Vasca Navale 79, 00146, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ioannis G.","family":"Tollis","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Crete, Heraklion, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2018,6,29]]},"reference":[{"key":"S0129054118410010BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.02.011"},{"key":"S0129054118410010BIB006","volume-title":"Graph Drawing","author":"Di Battista G.","year":"1999"},{"key":"S0129054118410010BIB008","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300004454"},{"key":"S0129054118410010BIB009","doi-asserted-by":"publisher","DOI":"10.1145\/568522.568523"},{"key":"S0129054118410010BIB011","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"S0129054118410010BIB012","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794277123"},{"issue":"2","key":"S0129054118410010BIB013","first-page":"114","volume":"4","author":"Ghoniem M.","year":"2005","journal-title":"InfoVis"},{"issue":"6","key":"S0129054118410010BIB014","first-page":"631","volume":"7","author":"Golovach P.","year":"2009","journal-title":"Discrete Mathematics and Applications"},{"issue":"1","key":"S0129054118410010BIB015","doi-asserted-by":"crossref","first-page":"87","DOI":"10.4213\/dm410","volume":"10","author":"Golovach P.","year":"1998","journal-title":"Disk. Mat."},{"key":"S0129054118410010BIB017","volume-title":"Handbook of Graph Drawing and Visualization","author":"Healy P.","year":"2013"},{"key":"S0129054118410010BIB018","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2007.70582"},{"key":"S0129054118410010BIB021","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"S0129054118410010BIB024","doi-asserted-by":"publisher","DOI":"10.1007\/BF02006264"},{"key":"S0129054118410010BIB026","doi-asserted-by":"publisher","DOI":"10.1006\/jvlc.1995.1010"},{"key":"S0129054118410010BIB028","doi-asserted-by":"publisher","DOI":"10.1016\/S0953-5438(00)00032-1"},{"key":"S0129054118410010BIB029","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1981.4308636"},{"key":"S0129054118410010BIB030","volume-title":"Computational aspects of VLSI","author":"Ullman J.","year":"1984"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054118410010","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T15:44:06Z","timestamp":1565106246000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054118410010"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6]]},"references-count":17,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2018,6,29]]},"published-print":{"date-parts":[[2018,6]]}},"alternative-id":["10.1142\/S0129054118410010"],"URL":"https:\/\/doi.org\/10.1142\/s0129054118410010","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6]]}}}