{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T11:12:35Z","timestamp":1778497955462,"version":"3.51.4"},"reference-count":5,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2006,10]]},"abstract":"<jats:p> We investigate the computational complexity of the following problem. Given a planar graph in which some vertices have already been placed in the plane, place the remaining vertices to form a planar straight-line drawing of the whole graph. We show that this extensibility problem, proposed in the 2003 \"Selected Open Problems in Graph Drawing\" [1], is NP-hard. <\/jats:p>","DOI":"10.1142\/s0129054106004261","type":"journal-article","created":{"date-parts":[[2006,9,18]],"date-time":"2006-09-18T12:04:43Z","timestamp":1158581083000},"page":"1061-1069","source":"Crossref","is-referenced-by-count":39,"title":["ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING"],"prefix":"10.1142","volume":"17","author":[{"given":"MAURIZIO","family":"PATRIGNANI","sequence":"first","affiliation":[{"name":"Dipartimento di Informatica e Automazione, Universit\u00e0 Roma Tre, Via della Vasca Navale, 79, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf3","first-page":"229","volume":"11","author":"Fary I.","journal-title":"Acta Sci. Math. Szeged"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1137\/0211025"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1951-0041425-5"},{"key":"rf7","volume-title":"Vorlesungen \u00fcber die Theorie der Polyeder","author":"Steinitz E.","year":"1934"},{"key":"rf8","first-page":"26","volume":"46","author":"Wagner K.","journal-title":"Jahresbericht der Deutschen Mathematiker-Vereinigung"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054106004261","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:40:35Z","timestamp":1565138435000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054106004261"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,10]]},"references-count":5,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2006,10]]}},"alternative-id":["10.1142\/S0129054106004261"],"URL":"https:\/\/doi.org\/10.1142\/s0129054106004261","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,10]]}}}