{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T11:13:13Z","timestamp":1778497993361,"version":"3.51.4"},"reference-count":15,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2010,4]]},"abstract":"<jats:p> We prove that computing a geometric minimum-dilation graph on a given set of points in the plane, using not more than a given number of edges, is an NP-hard problem, no matter if edge crossings are allowed or forbidden. We also show that the problem remains NP-hard even when a minimum-dilation tour or path is sought; not even an FPTAS exists in this case. <\/jats:p>","DOI":"10.1142\/s0218195910003244","type":"journal-article","created":{"date-parts":[[2010,4,21]],"date-time":"2010-04-21T07:38:07Z","timestamp":1271835487000},"page":"147-173","source":"Crossref","is-referenced-by-count":11,"title":["COMPUTING GEOMETRIC MINIMUM-DILATION GRAPHS IS NP-HARD"],"prefix":"10.1142","volume":"20","author":[{"given":"PANOS","family":"GIANNOPOULOS","sequence":"first","affiliation":[{"name":"Humboldt- Universit\u00e4t zu Berlin, Institut f\u00fcr Informatik, Unter den Linden 6, D-10099 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ROLF","family":"KLEIN","sequence":"additional","affiliation":[{"name":"Institute of Computer Science I, 53117 Bonn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"CHRISTIAN","family":"KNAUER","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Freie Universit\u00e4t Berlin, Takustra\u00dfe 9, D-14195 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MARTIN","family":"KUTZ","sequence":"additional","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik, 66123 Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D\u00c1NIEL","family":"MARX","sequence":"additional","affiliation":[{"name":"Humboldt-Universit\u00e4t zu Berlin, Institut f\u00fcr Informatik, Unter den Linden 6, D-10099 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,30]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.07.004"},{"key":"rf2","first-page":"1","volume":"3","author":"Brandes U.","journal-title":"Discr. Math. Theoret. Comput. Sci."},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90073-6"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480192237403"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.12.001"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1203-9"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50010-3"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.05.007"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1137\/050635675"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00226-2"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054109006486"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1137\/0211056"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1145\/1346330.1346336"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546884"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50021-8"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195910003244","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T08:21:14Z","timestamp":1565079674000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195910003244"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4]]},"references-count":15,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2012,4,30]]},"published-print":{"date-parts":[[2010,4]]}},"alternative-id":["10.1142\/S0218195910003244"],"URL":"https:\/\/doi.org\/10.1142\/s0218195910003244","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,4]]}}}