{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:36:55Z","timestamp":1787323015632,"version":"build-2736575974"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>We give an $O(n\\log ^3 n)$-time linear-space algorithm that, given a plane 3-tree $G$ with $n$ vertices and a set $S$ of $n$ points in the plane, determines whether $G$ has a point-set embedding on $S$ (i.e., a planar straight-line drawing of $G$ where each vertex is mapped to a distinct point of $S$), improving the $O(n^{4\/3+\\varepsilon})$-time $O(n^{4\/3})$-space algorithm of Moosa and Rahman [Lecture Notes in Comput. Sci. 6842, Springer, New York, 2011, pp. 204--212]. Given an arbitrary plane graph $G$ and a point set $S$, Kaufmann and Wiese [J. Graph Algorithms Appl., 6 (2002), pp. 115--129] gave an algorithm to compute 2-bend point-set embeddings of $G$ on $S$. Later, Di Giacomo and Liotta [Lecture Notes in Comput. Sci. 5942, Springer, New York, 2010, pp. 35--46] showed how such a drawing can be computed using $O(W^3)$ area, where $W$ is the length of the longest edge of the bounding box of $S$. Their algorithm uses $O(W^3)$ area even when the input graphs are restricted to plane 3-trees. We introduce new techniques for computing $2$-bend point-set embeddings of plane 3-trees that take only $O(W^2)$ area. We also give approximation algorithms for point-set embeddings of plane $3$-trees. Our results on 2-bend point-set embeddings and approximate point-set embeddings hold for partial plane $3$-trees (e.g., series-parallel graphs and Halin graphs).<\/jats:p>","DOI":"10.1137\/140964710","type":"journal-article","created":{"date-parts":[[2015,2,24]],"date-time":"2015-02-24T10:48:24Z","timestamp":1424774904000},"page":"405-420","source":"Crossref","is-referenced-by-count":2,"title":["Plane 3-Trees: Embeddability and Approximation"],"prefix":"10.1137","volume":"29","author":[{"given":"Stephane","family":"Durocher","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Debajyoti","family":"Mondal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,2,24]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.94.018702"},{"key":"atypb2","unstructured":"R. M. Baram,\n                      Polydisperse Granular Packings and Bearings\n                      , Ph.D. thesis, University of Stuttgart, Germany, 2005."},{"key":"atypb3","first-page":"41","author":"Biedl T.","year":"2012","journal-title":"ACM"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00002"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00069-4"},{"key":"atypb6","first-page":"515","author":"Brandenburg F. J.","year":"2004","journal-title":"New York"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.05.006"},{"key":"atypb8","first-page":"617","author":"Brodal G. S.","year":"2002","journal-title":"NJ"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00132"},{"key":"atypb10","first-page":"312","author":"Castan\u0342eda N.","year":"1996","journal-title":"Proceedings of CCCG"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758854"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/74074.74088"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"E. D. Demaine and A. Schulz,\n                      Embedding stacked polytopes on a polynomial-size grid\n                      , in Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, 2011, pp. 77-80.","DOI":"10.1137\/1.9781611973082.89"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122694"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.2307\/1969503"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"E. Di Giacomo, W. Didimo, G. Liotta, and S. K. Wismath,\n                      Curve-constrained drawings of planar graphs\n                      , Comput. Geom. (2005), pp. 1-23.","DOI":"10.1016\/j.comgeo.2004.04.002"},{"key":"atypb17","first-page":"35","author":"Di Giacomo E.","year":"2010","journal-title":"New York"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"V. Dujmovic\u0301, W. Evans, S. Lazard, W. Lenhart, G. Liotta, D. Rappaport, and S. K. Wismath,\n                      On point-sets that support planar graphs\n                      , Comput. Geom. (2012), pp. 29-50.","DOI":"10.1016\/j.comgeo.2012.03.003"},{"key":"atypb19","first-page":"148","author":"Durocher S.","year":"2012","journal-title":"New York"},{"key":"atypb20","first-page":"291","author":"Durocher S.","year":"2013","journal-title":"New York"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"S. Durocher, D. Mondal, R. I. Nishat, Md. S. Rahman, and S. Whitesides,\n                      Embedding plane 3-trees in $\\mathbb{R}^2$ and $\\mathbb{R}^3$\n                      , in Proceedings of the 19th International Symposium on Graph Drawing, Lecture Notes in Comput. Sci. 7034, Springer, New York, 2012.","DOI":"10.1007\/978-3-642-25878-7_5"},{"key":"atypb22","unstructured":"J. Erickson,\n                      On the relative complexities of some geometric problems\n                      , in Proceedings of the 7th Canadian Conference on Computational Geometry, 1995, pp. 85-90."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9149-3"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573994"},{"key":"atypb25","first-page":"207","author":"Katz B.","year":"2010","journal-title":"New York"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00046"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.06.009"},{"key":"atypb28","unstructured":"D. Mondal,\n                      Embedding a Planar Graph on a Given Point Set\n                      , Master's thesis, University of Manitoba, Canada, 2012."},{"key":"atypb29","first-page":"204","author":"Moosa T. Md.","year":"2011","journal-title":"New York"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2011.09.002"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90012-X"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1007\/PL00007258"},{"key":"atypb33","unstructured":"W. Schnyder,\n                      Embedding planar graphs on the grid\n                      , in Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, 1990, pp. 138-148."},{"key":"atypb34","first-page":"151","author":"Shamos M. I.","year":"1975","journal-title":"IEEE"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(97)00027-8"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1109\/21.87055"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140964710","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:37:07Z","timestamp":1787319427000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140964710"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140964710"],"URL":"https:\/\/doi.org\/10.1137\/140964710","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}