{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T05:08:58Z","timestamp":1648616938258},"reference-count":15,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2012,3]]},"abstract":"<jats:p> In the point-set embeddability problem, we are given a plane graph G with n vertices and a point set S with the same number of points. Now the goal is to answer the question whether there exists a straight-line drawing of G such that each vertex is represented as a distinct point of S as well as to provide an embedding if one does exist. This problem has recently been solved in O(n<jats:sup>2<\/jats:sup> log n) time for plane 3-trees. In this paper, we present a new efficient algorithm with time complexity O(n<jats:sup>4\/3+\u03f5<\/jats:sup> log n). We also present an O(nk<jats:sup>4<\/jats:sup>) time algorithm for the case when |S| = k &gt; n. This is a significant improvement over the best algorithm for this case in the literature, which runs in O(nk<jats:sup>8<\/jats:sup>) time. <\/jats:p>","DOI":"10.1142\/s1793830912500097","type":"journal-article","created":{"date-parts":[[2012,4,9]],"date-time":"2012-04-09T21:24:02Z","timestamp":1334006642000},"page":"1250009","source":"Crossref","is-referenced-by-count":0,"title":["IMPROVED ALGORITHMS FOR THE POINT-SET EMBEDDABILITY PROBLEM FOR PLANE 3-TREES"],"prefix":"10.1142","volume":"04","author":[{"given":"TANAEEM M.","family":"MOOSA","sequence":"first","affiliation":[{"name":"A\u2113EDA Group, Department of Computer Science and Engineering (CSE), Bangledesh University of Engineering and Technology (BUET), Dhaka-1000, Bangladesh"}]},{"given":"M. SOHEL","family":"RAHMAN","sequence":"additional","affiliation":[{"name":"A\u2113EDA Group, Department of Computer Science and Engineering (CSE), Bangledesh University of Engineering and Technology (BUET), Dhaka-1000, Bangladesh"}]}],"member":"219","published-online":{"date-parts":[[2012,4,13]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73951-7_10"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00069-4"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00132"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/BF02770864"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758854"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2007.07.081"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00158"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054106004273"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573994"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00191-2"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195905001671"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2011.09.002"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1142\/5648"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1007\/PL00007258"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90033-7"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830912500097","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T13:53:43Z","timestamp":1565186023000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830912500097"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3]]},"references-count":15,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2012,4,13]]},"published-print":{"date-parts":[[2012,3]]}},"alternative-id":["10.1142\/S1793830912500097"],"URL":"https:\/\/doi.org\/10.1142\/s1793830912500097","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3]]}}}