{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T21:40:03Z","timestamp":1745962803876,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642367625"},{"type":"electronic","value":"9783642367632"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-36763-2_25","type":"book-chapter","created":{"date-parts":[[2013,2,14]],"date-time":"2013-02-14T03:17:33Z","timestamp":1360811853000},"page":"279-290","source":"Crossref","is-referenced-by-count":1,"title":["Kinetic and Stationary Point-Set Embeddability for Plane Graphs"],"prefix":"10.1007","author":[{"given":"Zahed","family":"Rahmati","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sue H.","family":"Whitesides","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Valerie","family":"King","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"25_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/978-3-642-31155-0_5","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"M.A. Abam","year":"2012","unstructured":"Abam, M.A., Rahmati, Z., Zarei, A.: Kinetic Pie Delaunay Graph and Its Applications. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol.\u00a07357, pp. 48\u201358. Springer, Heidelberg (2012)"},{"key":"25_CR2","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Eppstein, D., Guibas, L.J., Henzinger, M.R.: Parametric and kinetic minimum spanning trees. In: FOCS, pp. 596\u2013605. IEEE Computer Society (1998)","DOI":"10.1109\/SFCS.1998.743510"},{"key":"25_CR3","first-page":"1","volume":"5","author":"P.K. Agarwal","year":"2008","unstructured":"Agarwal, P.K., Kaplan, H., Sharir, M.: Kinetic and dynamic data structures for closest pair and all nearest neighbors. ACM Trans. Algorithms 5, 4:1\u20134:37 (2008)","journal-title":"ACM Trans. Algorithms"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"Basch, J.: Kinetic data structures. PhD Thesis, Stanford University (1999)","DOI":"10.1145\/304893.305004"},{"key":"25_CR5","unstructured":"Basch, J., Guibas, L.J., Hershberger, J.: Data structures for mobile data. In: Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1997, pp. 747\u2013756. Society for Industrial and Applied Mathematics (1997)"},{"key":"25_CR6","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/2261250.2261257","volume-title":"Proceedings of the 28th Symposuim on Computational Geometry, SoCG 2012","author":"T. Biedl","year":"2012","unstructured":"Biedl, T., Vatshelle, M.: The point-set embeddability problem for plane graphs. In: Proceedings of the 28th Symposuim on Computational Geometry, SoCG 2012, pp. 41\u201350. ACM, New York (2012)"},{"issue":"3","key":"25_CR7","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. Comput. Geom.\u00a023(3), 303\u2013312 (2002)","journal-title":"Comput. Geom."},{"key":"25_CR8","doi-asserted-by":"crossref","unstructured":"Bose, P., McAllister, M., Snoeyink, J.: Optimal algorithms to embed trees in a point set. J. Graph Algorithms Appl. 1 (1997)","DOI":"10.7155\/jgaa.00002"},{"issue":"2","key":"25_CR9","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. J. Graph Algorithms Appl.\u00a010(2), 353\u2013363 (2006)","journal-title":"J. Graph Algorithms Appl."},{"issue":"1","key":"25_CR10","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1023\/A:1021998507140","volume":"7","author":"C. Chen","year":"2003","unstructured":"Chen, C.: Any maximal planar graph with only one separating triangle is hamiltonian. J. Comb. Optim.\u00a07(1), 79\u201386 (2003)","journal-title":"J. Comb. Optim."},{"issue":"2","key":"25_CR11","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0196-6774(89)90012-6","volume":"10","author":"N. Chiba","year":"1989","unstructured":"Chiba, N., Nishizeki, T.: The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs. J. Algorithms\u00a010(2), 187\u2013211 (1989)","journal-title":"J. Algorithms"},{"issue":"1","key":"25_CR12","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/0214017","volume":"14","author":"N. Chiba","year":"1985","unstructured":"Chiba, N., Nishizeki, T.: Arboricity and subgraph listing algorithms. SIAM J. Comput.\u00a014(1), 210\u2013223 (1985)","journal-title":"SIAM J. Comput."},{"key":"25_CR13","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)"},{"issue":"1","key":"25_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.comgeo.2004.04.002","volume":"30","author":"E.D. Giacomo","year":"2005","unstructured":"Giacomo, E.D., Didimo, W., Liotta, G., Wismath, S.K.: Curve-constrained drawings of planar graphs. Computational Geometry\u00a030(1), 1\u201323 (2005)","journal-title":"Computational Geometry"},{"key":"25_CR15","doi-asserted-by":"publisher","first-page":"165","DOI":"10.2307\/2323956","volume":"98","author":"P. Gritzmann","year":"1991","unstructured":"Gritzmann, P., Mohar, B., Pach, J., Pollack, R.: Embedding a planar triangulation with vertices at specified points. American Mathematical Monthly\u00a098, 165\u2013166 (1991)","journal-title":"American Mathematical Monthly"},{"key":"25_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/3-540-55121-2_11","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"L.J. Guibas","year":"1992","unstructured":"Guibas, L.J., Mitchell, J.S.B.: Voronoi Diagrams of Moving Points in the Plane. In: Schmidt, G., Berghammer, R. (eds.) WG 1991. LNCS, vol.\u00a0570, pp. 113\u2013125. Springer, Heidelberg (1992)"},{"issue":"14","key":"25_CR17","doi-asserted-by":"publisher","first-page":"1833","DOI":"10.1016\/j.dam.2007.03.018","volume":"155","author":"G. Helden","year":"2007","unstructured":"Helden, G.: Each maximal planar graph with exactly two separating triangles is hamiltonian. Discrete Applied Mathematics\u00a0155(14), 1833\u20131836 (2007)","journal-title":"Discrete Applied Mathematics"},{"key":"25_CR18","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 & Computational Geometry\u00a011, 51\u201363 (1994)","journal-title":"Discrete & Computational Geometry"},{"issue":"1","key":"25_CR19","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. Graph Algorithms Appl.\u00a06(1), 115\u2013129 (2002)","journal-title":"J. Graph Algorithms Appl."},{"key":"25_CR20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1706591.1706597","volume":"57","author":"G. Nivasch","year":"2010","unstructured":"Nivasch, G.: Improved bounds and new techniques for Davenport\u2013Schinzel sequences and their generalizations. J. ACM 57, 17:1\u201317:44 (2010)","journal-title":"J. ACM"},{"key":"25_CR21","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.jda.2012.04.009","volume":"16","author":"Z. Rahmati","year":"2012","unstructured":"Rahmati, Z., Zarei, A.: Kinetic Euclidean minimum spanning tree in the plane. Journal of Discrete Algorithms\u00a016, 2\u201311 (2012)","journal-title":"Journal of Discrete Algorithms"},{"key":"25_CR22","volume-title":"Davenport-Schinzel Sequences and their Geometric Applications","author":"M. Sharir","year":"2010","unstructured":"Sharir, M., Agarwal, P.K.: Davenport-Schinzel Sequences and their Geometric Applications. Cambridge University Press, New York (2010)"},{"key":"25_CR23","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1090\/S0002-9947-1956-0081471-8","volume":"82","author":"W. Tutte","year":"1956","unstructured":"Tutte, W.: A theorem on planar graphs. Trans. Amer. Math. Soc.\u00a082, 99\u2013116 (1956)","journal-title":"Trans. Amer. Math. Soc."},{"key":"25_CR24","doi-asserted-by":"publisher","first-page":"378","DOI":"10.2307\/1968197","volume":"32","author":"H. Whitney","year":"1931","unstructured":"Whitney, H.: A theorem on graphs. Ann. Math.\u00a032, 378\u2013390 (1931)","journal-title":"Ann. Math."}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-36763-2_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T21:16:15Z","timestamp":1745961375000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-36763-2_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642367625","9783642367632"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-36763-2_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}