{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T20:21:57Z","timestamp":1725740517317},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642401039"},{"type":"electronic","value":"9783642401046"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40104-6_26","type":"book-chapter","created":{"date-parts":[[2013,7,11]],"date-time":"2013-07-11T05:36:30Z","timestamp":1373520990000},"page":"291-303","source":"Crossref","is-referenced-by-count":0,"title":["Plane 3-trees: Embeddability and Approximation"],"prefix":"10.1007","author":[{"given":"Stephane","family":"Durocher","sequence":"first","affiliation":[]},{"given":"Debajyoti","family":"Mondal","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"26_CR1","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF02122694","volume":"10","author":"H. Fraysseix de","year":"1990","unstructured":"de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica\u00a010(1), 41\u201351 (1990)","journal-title":"Combinatorica"},{"key":"26_CR2","unstructured":"Schnyder, W.: Embedding planar graphs on the grid. In: SODA, pp. 138\u2013148. ACM (1990)"},{"issue":"3","key":"26_CR3","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/S0925-7721(01)00069-4","volume":"23","author":"P. Bose","year":"2002","unstructured":"Bose, P.: On embedding an outer-planar graph in a point set. Computational Geometry: Theory and Applications\u00a023(3), 303\u2013312 (2002)","journal-title":"Computational Geometry: Theory and Applications"},{"issue":"2","key":"26_CR4","doi-asserted-by":"publisher","first-page":"353","DOI":"10.7155\/jgaa.00132","volume":"10","author":"S. Cabello","year":"2006","unstructured":"Cabello, S.: Planar embeddability of the vertices of a graph using a fixed point set is NP-hard. Journal of Graph Algorithms and Applications\u00a010(2), 353\u2013363 (2006)","journal-title":"Journal of Graph Algorithms and Applications"},{"issue":"1","key":"26_CR5","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/BF02573994","volume":"11","author":"Y. Ikebe","year":"1994","unstructured":"Ikebe, Y., Perles, M.A., Tamura, A., Tokunaga, S.: The rooted tree embedding problem into points in the plane. Discrete & Comp. Geometry\u00a011(1), 51\u201363 (1994)","journal-title":"Discrete & Comp. Geometry"},{"issue":"2","key":"26_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.7155\/jgaa.00002","volume":"1","author":"P. Bose","year":"1997","unstructured":"Bose, P., McAllister, M., Snoeyink, J.: Optimal algorithms to embed trees in a point set. Journal of Graph Algorithms and Applications\u00a01(2), 1\u201315 (1997)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"26_CR7","doi-asserted-by":"crossref","unstructured":"Casta\u00f1eda, N., Urrutia, J.: Straight line embeddings of planar graphs on point sets. In: CCCG, pp. 312\u2013318 (1996)","DOI":"10.1515\/9780773591134-055"},{"key":"26_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/978-3-642-28076-4_16","volume-title":"WALCOM: Algorithms and Computation","author":"S. Durocher","year":"2012","unstructured":"Durocher, S., Mondal, D.: On the hardness of point-set embeddability. In: Rahman, M.S., Nakano, S.-I. (eds.) WALCOM 2012. LNCS, vol.\u00a07157, pp. 148\u2013159. Springer, Heidelberg (2012)"},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"Biedl, T., Vatshelle, M.: The point-set embeddability problem for plane graphs. In: SoCG, pp. 41\u201350. ACM (2012)","DOI":"10.1145\/2261250.2261257"},{"key":"26_CR10","doi-asserted-by":"crossref","unstructured":"Andrade Jr., J.S., Herrmann, H.J., Andrade, R.F.S., da Silva, L.R.: Apollonian networks: Simultaneously scale-free, small world, euclidean, space filling, and with matching graphs. Physical Review Letters\u00a094 (2005)","DOI":"10.1103\/PhysRevLett.94.018702"},{"issue":"3","key":"26_CR11","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/j.comgeo.2011.09.002","volume":"45","author":"R.I. Nishat","year":"2012","unstructured":"Nishat, R.I., Mondal, D., Rahman, M.S.: Point-set embeddings of plane 3-trees. Computational Geometry: Theory and Applications\u00a045(3), 88\u201398 (2012)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"26_CR12","series-title":"Lecture Notes in Computer Science","first-page":"39","volume-title":"GD 2011","author":"S. Durocher","year":"2011","unstructured":"Durocher, S., Mondal, D., Nishat, R.I., Rahman, M.S., Whitesides, S.: Embedding plane 3-trees in \u211d2 and \u211d3. In: Speckmann, B. (ed.) GD 2011. LNCS, vol.\u00a07034, pp. 39\u201351. Springer, Heidelberg (2011)"},{"key":"26_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1007\/978-3-642-22685-4_18","volume-title":"Computing and Combinatorics","author":"T.M. Moosa","year":"2011","unstructured":"Moosa, T.M., Sohel Rahman, M.: Improved algorithms for the point-set embeddability problem for plane 3-trees. In: Fu, B., Du, D.-Z. (eds.) COCOON 2011. LNCS, vol.\u00a06842, pp. 204\u2013212. Springer, Heidelberg (2011)"},{"key":"26_CR14","unstructured":"Erickson, J.: On the relative complexities of some geometric problems. In: CCCG, pp. 85\u201390 (1995)"},{"key":"26_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/978-3-540-24595-7_55","volume-title":"Graph Drawing","author":"F.J. Brandenburg","year":"2004","unstructured":"Brandenburg, F.J., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Liotta, G., Mutzel, P.: Selected open problems in graph drawing. In: Liotta, G. (ed.) GD 2003. LNCS, vol.\u00a02912, pp. 515\u2013539. Springer, Heidelberg (2004)"},{"issue":"2","key":"26_CR16","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/s00454-009-9149-3","volume":"43","author":"H. Everett","year":"2010","unstructured":"Everett, H., Lazard, S., Liotta, G., Wismath, S.K.: Universal sets of n points for one-bend drawings of planar graphs with n vertices. Discrete & Computational Geometry\u00a043(2), 272\u2013288 (2010)","journal-title":"Discrete & Computational Geometry"},{"issue":"1","key":"26_CR17","doi-asserted-by":"publisher","first-page":"115","DOI":"10.7155\/jgaa.00046","volume":"6","author":"M. Kaufmann","year":"2002","unstructured":"Kaufmann, M., Wiese, R.: Embedding vertices at points: Few bends suffice for planar graphs. J. of Graph Algorithms and Applications\u00a06(1), 115\u2013129 (2002)","journal-title":"J. of Graph Algorithms and Applications"},{"key":"26_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/978-3-642-11440-3_4","volume-title":"WALCOM: Algorithms and Computation","author":"E. Giacomo Di","year":"2010","unstructured":"Di Giacomo, E., Liotta, G.: The Hamiltonian augmentation problem and its applications to graph drawing. In: Rahman, M. S., Fujita, S. (eds.) WALCOM 2010. LNCS, vol.\u00a05942, pp. 35\u201346. Springer, Heidelberg (2010)"},{"issue":"5&6","key":"26_CR19","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/BF01758854","volume":"8","author":"B. Chazelle","year":"1992","unstructured":"Chazelle, B., Sharir, M., Welzl, E.: Quasi-optimal upper bounds for simplex range searching and new zone theorems. Algorithmica\u00a08(5&6), 407\u2013429 (1992)","journal-title":"Algorithmica"},{"issue":"1","key":"26_CR20","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/S0925-7721(97)00027-8","volume":"10","author":"W.L. Steiger","year":"1998","unstructured":"Steiger, W.L., Streinu, I.: Illumination by floodlights. Computational Geometry: Theory and Applications\u00a010(1), 57\u201370 (1998)","journal-title":"Computational Geometry: Theory and Applications"},{"issue":"2","key":"26_CR21","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","volume":"23","author":"M.H. Overmars","year":"1981","unstructured":"Overmars, M.H., van Leeuwen, J.: Maintenance of configurations in the plane. Journal of Computer and System Sciences\u00a023(2), 166\u2013204 (1981)","journal-title":"Journal of Computer and System Sciences"},{"key":"26_CR22","unstructured":"Brodal, G.S., Jacob, R.: Dynamic planar convex hull. In: FOCS, pp. 617\u2013626. IEEE (2002)"},{"issue":"1","key":"26_CR23","doi-asserted-by":"publisher","first-page":"161","DOI":"10.2307\/1969503","volume":"51","author":"R.P. Dilworth","year":"1950","unstructured":"Dilworth, R.P.: A decomposition theorem for partially ordered sets. Annals of Mathematics\u00a051(1), 161\u2013166 (1950)","journal-title":"Annals of Mathematics"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40104-6_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T10:30:01Z","timestamp":1715682601000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40104-6_26"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642401039","9783642401046"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40104-6_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}