{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:48:23Z","timestamp":1759063703149,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642118043"},{"type":"electronic","value":"9783642118050"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-11805-0_21","type":"book-chapter","created":{"date-parts":[[2010,3,5]],"date-time":"2010-03-05T07:45:33Z","timestamp":1267775133000},"page":"207-218","source":"Crossref","is-referenced-by-count":20,"title":["Manhattan-Geodesic Embedding of Planar Graphs"],"prefix":"10.1007","author":[{"given":"Bastian","family":"Katz","sequence":"first","affiliation":[]},{"given":"Marcus","family":"Krug","sequence":"additional","affiliation":[]},{"given":"Ignaz","family":"Rutter","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"Wolff","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"21_CR1","doi-asserted-by":"crossref","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."},{"key":"21_CR2","unstructured":"Demaine, E.: Simple polygonizations (2007), \n                    \n                      http:\/\/erikdemaine.org\/polygonization\/\n                    \n                    \n                   (Accessed May 30, 2009)"},{"key":"21_CR3","volume-title":"Computers and Intractability. A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"Goaoc, X., Kratochv\u00edl, J., Okamoto, Y., Shin, C.-S., Spillner, A., Wolff, A.: Untangling a planar graph. Discrete Comput. Geom (2009), \n                    \n                      http:\/\/dx.doi.org\/10.1007\/s00454-008-9130-6","DOI":"10.1007\/s00454-008-9130-6"},{"key":"21_CR5","unstructured":"Hurtado, F.: Personal communication (2006)"},{"key":"21_CR6","unstructured":"Katz, B., Krug, M., Rutter, I., Wolff, A.: Manhattan-geodesic point-set embeddability and polygonization. Technical Report 2009-17, Universit\u00e4t Karlsruhe (2009), \n                    \n                      http:\/\/digbib.ubka.uni-karlsruhe.de\/volltexte\/1000012949"},{"issue":"1","key":"21_CR7","doi-asserted-by":"crossref","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."},{"issue":"2","key":"21_CR8","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/BF02006154","volume":"8","author":"Y. Liu","year":"1992","unstructured":"Liu, Y., Marchioro, P., Petreschi, R., Simeone, B.: Theoretical results on at most 1-bend embeddability of graphs. Acta Math. Appl. Sinica (English Ser.)\u00a08(2), 188\u2013192 (1992)","journal-title":"Acta Math. Appl. Sinica (English Ser.)"},{"key":"21_CR9","first-page":"97","volume-title":"Computational Morphology","author":"J. O\u2019Rourke","year":"1988","unstructured":"O\u2019Rourke, J.: Uniqueness of orthogonal connect-the-dots. In: Toussaint, G. (ed.) Computational Morphology, pp. 97\u2013104. North-Holland, Amsterdam (1988)"},{"issue":"4","key":"21_CR10","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. Graph. Combinator.\u00a017(4), 717\u2013728 (2001)","journal-title":"Graph. Combinator."},{"issue":"2","key":"21_CR11","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1016\/0196-6774(86)90006-4","volume":"7","author":"R. Raghavan","year":"1986","unstructured":"Raghavan, R., Cohoon, J., Sahni, S.: Single bend wiring. J. Algorithms\u00a07(2), 232\u2013257 (1986)","journal-title":"J. Algorithms"},{"key":"21_CR12","unstructured":"Rappaport, D.: On the complexity of computing orthogonal polygons from a set of points. Technical Report SOCS-86.9, McGill University, Montr\u00e9al (1986)"},{"issue":"1-3","key":"21_CR13","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0012-365X(93)90124-C","volume":"119","author":"F. Rendl","year":"1993","unstructured":"Rendl, F., Woeginger, G.: Reconstructing sets of orthogonal line segments in the plane. Discrete Math\u00a0119(1-3), 167\u2013174 (1993)","journal-title":"Discrete Math"},{"key":"21_CR14","unstructured":"Schnyder, W.: Embedding planar graphs on the grid. In: Proc. 1st ACM-SIAM Symp. on Discrete Algorithms (SODA 1990), pp. 138\u2013148 (1990)"},{"issue":"3","key":"21_CR15","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1137\/0216030","volume":"16","author":"R. Tamassia","year":"1987","unstructured":"Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput.\u00a016(3), 421\u2013444 (1987)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11805-0_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:44:01Z","timestamp":1606185841000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-11805-0_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642118043","9783642118050"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11805-0_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}