{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,7]],"date-time":"2025-12-07T21:28:44Z","timestamp":1765142924636},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2010,10]]},"abstract":"<jats:p> This paper starts the investigation of a constrained version of the point-set embed-dability problem. Let G = (V,E) be a planar graph with n vertices, G\u2032 = (V\u2032,E\u2032) a subgraph of G, and S a set of n distinct points in the plane. We study the problem of computing a point-set embedding of G on S subject to the constraint that G\u2032 is drawn with straight-line edges. Different drawing algorithms are presented that guarantee small curve complexity of the resulting drawing, i.e. a small number of bends per edge. It is proved that: <\/jats:p><jats:p> \u2022 If G\u2032 is an outerplanar graph and S is any set of points in convex position, a point-set embedding of G on S can be computed such that the edges of E\\E\u2032 have at most 4 bends each. <\/jats:p><jats:p> \u2022 If S is any set of points in general position and G\u2032 is a face of G or if it is a simple path, the curve complexity of the edges of E\\E\u2032 is at most 8. <\/jats:p><jats:p> \u2022 If S is in general position and G\u2032 is a set of k disjoint paths, the curve complexity of the edges of E \\ E\u2032 is O(2<jats:sup>k<\/jats:sup>). <\/jats:p>","DOI":"10.1142\/s021819591000344x","type":"journal-article","created":{"date-parts":[[2010,11,1]],"date-time":"2010-11-01T05:26:48Z","timestamp":1288589208000},"page":"577-600","source":"Crossref","is-referenced-by-count":5,"title":["CONSTRAINED POINT-SET EMBEDDABILITY OF PLANAR GRAPHS"],"prefix":"10.1142","volume":"20","author":[{"given":"EMILIO","family":"DI GIACOMO","sequence":"first","affiliation":[{"name":"Dipartimento di Ingegneria Elettronica e dell'Informazione, Universit\u00e0 degli Studi di Perugia, Via G. Duranti 93, 06125 Perugia, Italy"}]},{"given":"WALTER","family":"DIDIMO","sequence":"additional","affiliation":[{"name":"Dipartimento di Ingegneria Elettronica e dell'Informazione, Universit\u00e0 degli Studi di Perugia, Via G. Duranti 93, 06125 Perugia, Italy"}]},{"given":"GIUSEPPE","family":"LIOTTA","sequence":"additional","affiliation":[{"name":"Dipartimento di Ingegneria Elettronica e dell'Informazione, Universit\u00e0 degli Studi di Perugia, Via G. Duranti 93, 06125 Perugia, Italy"}]},{"given":"HENK","family":"MEIJER","sequence":"additional","affiliation":[{"name":"Science Department, Roosevelt Academy, P.O. Box 94, NL-4330 AB Middelburg, The Netherlands"}]},{"given":"STEPHEN K.","family":"WISMATH","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, University of Lethbridge, 4401 University Dr., Lethbridge, Alberta, Canada"}]}],"member":"219","published-online":{"date-parts":[[2012,4,30]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1142\/9789812777898"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(91)90052-V"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/PL00007258"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.08.004"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00006"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573994"},{"key":"rf7","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1090\/dimacs\/009\/11","volume":"9","author":"Pach J.","journal-title":"Planar Graphs (DIMACS Series in Discrete Mathematics and Theoretical Computer Science)"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00069-4"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.2307\/2323956"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00046"},{"key":"rf11","first-page":"29","volume":"11","author":"Di Giacomo E.","journal-title":"J. Graph Algorith. Appl."},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054106004273"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9255-2"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00191-2"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195905001671"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2009.01.001"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.04.002"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122694"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S021819591000344X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T23:37:38Z","timestamp":1565134658000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S021819591000344X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10]]},"references-count":18,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2012,4,30]]},"published-print":{"date-parts":[[2010,10]]}},"alternative-id":["10.1142\/S021819591000344X"],"URL":"https:\/\/doi.org\/10.1142\/s021819591000344x","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10]]}}}