{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:26:31Z","timestamp":1760441191418},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319038407"},{"type":"electronic","value":"9783319038414"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-319-03841-4_33","type":"book-chapter","created":{"date-parts":[[2013,12,2]],"date-time":"2013-12-02T00:28:55Z","timestamp":1385944135000},"page":"376-387","source":"Crossref","is-referenced-by-count":6,"title":["Minimum Length Embedding of Planar Graphs at Fixed Vertex Locations"],"prefix":"10.1007","author":[{"given":"Timothy M.","family":"Chan","sequence":"first","affiliation":[]},{"given":"Hella-Franziska","family":"Hoffmann","sequence":"additional","affiliation":[]},{"given":"Stephen","family":"Kiazyk","sequence":"additional","affiliation":[]},{"given":"Anna","family":"Lubiw","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"33_CR1","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/PL00007258","volume":"17","author":"J. Pach","year":"2001","unstructured":"Pach, J., Wenger, R.: Embedding planar graphs at fixed vertex locations. Graphs and Combinatorics\u00a017(4), 717\u2013728 (2001)","journal-title":"Graphs and Combinatorics"},{"key":"33_CR2","unstructured":"Sam Loyd, J.: Sam Loyd\u2019s Cyclopedia of 5000 Puzzles Tricks and Conundrums. Lamb Publishing Company (1914)"},{"key":"33_CR3","doi-asserted-by":"crossref","unstructured":"Angelini, P., Di Battista, G., Frati, F., Jel\u00ednek, V., Kratochv\u00edl, J., Patrignani, M., Rutter, I.: Testing planarity of partially embedded graphs. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 202\u2013221 (2010)","DOI":"10.1137\/1.9781611973075.19"},{"issue":"1","key":"33_CR4","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1287\/ijoc.7.1.84","volume":"7","author":"T.M. Liebling","year":"1995","unstructured":"Liebling, T.M., Margot, F., M\u00fcller, D., Prodon, A., Stauffer, L.: Disjoint paths in the plane. ORSA Journal on Computing\u00a07(1), 84\u201388 (1995)","journal-title":"ORSA Journal on Computing"},{"key":"33_CR5","unstructured":"Bastert, O., Fekete, S.P.: Geometric wire routing. Technical Report 332, Angewandte Mathematik und Informatik, Universit\u00e4t zu K\u00f6ln (1996) (in German)"},{"key":"33_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/BFb0009507","volume-title":"Algorithms and Computation","author":"E. Papadopoulou","year":"1996","unstructured":"Papadopoulou, E.: k-pairs non-crossing shortest paths in a simple polygon. In: Nagamochi, H., Suri, S., Igarashi, Y., Miyano, S., Asano, T. (eds.) ISAAC 1996. LNCS, vol.\u00a01178, pp. 305\u2013314. Springer, Heidelberg (1996)"},{"key":"33_CR7","doi-asserted-by":"crossref","unstructured":"Erickson, J., Nayyeri, A.: Shortest non-crossing walks in the plane. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 297\u2013308 (2011)","DOI":"10.1137\/1.9781611973082.25"},{"key":"33_CR8","unstructured":"Polishchuk, V., Mitchell, J.S.: Touring convex bodies \u2013 a conic programming solution. In: Proceedings of the 17th Canadian Conference on Computational Geometry, pp. 290\u2013293 (2005)"},{"key":"33_CR9","doi-asserted-by":"crossref","unstructured":"Dror, M., Efrat, A., Lubiw, A., Mitchell, J.S.B.: Touring a sequence of polygons. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), pp. 473\u2013482 (2003)","DOI":"10.1145\/780611.780612"},{"issue":"5","key":"33_CR10","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1142\/S0129054106004261","volume":"17","author":"M. Patrignani","year":"2006","unstructured":"Patrignani, M.: On extending a partial straight-line drawing. International Journal of Foundations of Computer Science\u00a017(5), 1061\u20131069 (2006)","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"2","key":"33_CR11","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/S0196-6774(03)00090-7","volume":"49","author":"S. Bespamyatnikh","year":"2003","unstructured":"Bespamyatnikh, S.: Computing homotopic shortest paths in the plane. Journal of Algorithms\u00a049(2), 284\u2013303 (2003)","journal-title":"Journal of Algorithms"},{"issue":"3","key":"33_CR12","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1016\/j.comgeo.2006.03.003","volume":"35","author":"A. Efrat","year":"2006","unstructured":"Efrat, A., Kobourov, S.G., Lubiw, A.: Computing homotopic shortest paths efficiently. Computational Geometry\u00a035(3), 162\u2013172 (2006)","journal-title":"Computational Geometry"},{"issue":"5","key":"33_CR13","doi-asserted-by":"publisher","first-page":"1143","DOI":"10.1142\/S0129054106004315","volume":"17","author":"C.A. Duncan","year":"2006","unstructured":"Duncan, C.A., Efrat, A., Kobourov, S.G., Wenk, C.: Drawing with fat edges. International Journal of Foundations of Computer Science\u00a017(5), 1143\u20131164 (2006)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"33_CR14","doi-asserted-by":"crossref","unstructured":"Mitchell, J.S., Polishchuk, V.: Thick non-crossing paths and minimum-cost flows in polygonal domains. In: Proceedings of the 23rd Annual Symposium on Computational Geometry (SoCG), pp. 56\u201365 (2007)","DOI":"10.1145\/1247069.1247079"},{"issue":"2","key":"33_CR15","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":"33_CR16","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.comgeo.2012.03.003","volume":"46","author":"V. Dujmovi\u0107","year":"2013","unstructured":"Dujmovi\u0107, V., Evans, W.S., Lazard, S., Lenhart, W., Liotta, G., Rappaport, D., Wismath, S.K.: On point-sets that support planar graphs. Computational Geometry\u00a046(1), 29\u201350 (2013)","journal-title":"Computational Geometry"},{"key":"33_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/978-3-642-11805-0_21","volume-title":"Graph Drawing","author":"B. Katz","year":"2010","unstructured":"Katz, B., Krug, M., Rutter, I., Wolff, A.: Manhattan-geodesic embedding of planar graphs. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol.\u00a05849, pp. 207\u2013218. Springer, Heidelberg (2010)"},{"issue":"3","key":"33_CR18","doi-asserted-by":"publisher","first-page":"468","DOI":"10.1016\/0196-6774(92)90050-M","volume":"13","author":"F. Hwang","year":"1992","unstructured":"Hwang, F., Weng, J.: The shortest network under a given topology. Journal of Algorithms\u00a013(3), 468\u2013488 (1992)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"33_CR19","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0166-218X(93)90092-3","volume":"47","author":"P. Winter","year":"1993","unstructured":"Winter, P.: Euclidean Steiner minimal trees with obstacles and Steiner visibility graphs. Discrete Applied Mathematics\u00a047(2), 187\u2013206 (1993)","journal-title":"Discrete Applied Mathematics"},{"key":"33_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/978-3-642-28076-4_19","volume-title":"WALCOM: Algorithms and Computation","author":"M. Fink","year":"2012","unstructured":"Fink, M., Haunert, J.-H., Mchedlidze, T., Spoerhase, J., Wolff, A.: Drawing graphs with vertices at specified positions and crossings at large angles. In: Rahman, M. S., Nakano, S.-i. (eds.) WALCOM 2012. LNCS, vol.\u00a07157, pp. 186\u2013197. Springer, Heidelberg (2012)"},{"key":"33_CR21","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/978-1-4614-0110-0_17","volume-title":"Thirty Essays on Geometric Graph Theory","author":"F. Hurtado","year":"2013","unstructured":"Hurtado, F., T\u00f3th, C.: Plane geometric graph augmentation: A generic perspective. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 327\u2013354. Springer, New York (2013)"},{"issue":"3","key":"33_CR22","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/BF01955681","volume":"16","author":"J. Takahashi","year":"1996","unstructured":"Takahashi, J., Suzuki, H., Nishizeki, T.: Shortest noncrossing paths in plane graphs. Algorithmica\u00a016(3), 339\u2013357 (1996)","journal-title":"Algorithmica"},{"key":"33_CR23","doi-asserted-by":"crossref","unstructured":"Kamousi, P., Chan, T.M., Suri, S.: Stochastic minimum spanning trees in Euclidean spaces. In: Proceedings of the 27th Annual ACM Symposium on Computational Geometry (SoCG), pp. 65\u201374 (2011)","DOI":"10.1145\/1998196.1998206"},{"issue":"2","key":"33_CR24","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1137\/0215024","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., O\u2019Rourke, J., Seidel, R.: Constructing arrangements of lines and hyperplanes with applications. SIAM Journal on Computing\u00a015(2), 341\u2013363 (1986)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-03841-4_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T21:48:55Z","timestamp":1558734535000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-03841-4_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783319038407","9783319038414"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-03841-4_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}