{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:25:49Z","timestamp":1759638349030},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1997,4,1]],"date-time":"1997-04-01T00:00:00Z","timestamp":859852800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[1997,4]]},"DOI":"10.1007\/pl00009290","type":"journal-article","created":{"date-parts":[[2006,2,17]],"date-time":"2006-02-17T12:37:41Z","timestamp":1140179861000},"page":"339-358","source":"Crossref","is-referenced-by-count":20,"title":["Grid Embedding of 4-Connected Plane Graphs"],"prefix":"10.1007","volume":"17","author":[{"given":"Xin","family":"He","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"170300339_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph Theory with Applications","author":"J. Bondy","year":"1976","unstructured":"J. Bondy and U. Murty, Graph Theory with Applications, North-Holland, Amsterdam, 1976."},{"key":"170300339_CR2","unstructured":"N. Chiba, T. Yamanouchi, and T. Nishizeki, Linear algorithms for convex drawings of planar graphs, in Progress in Graph Theory, J. A. Bondy and U. S. R. Murty (eds.), 1982, pp. 153\u2013173."},{"key":"170300339_CR3","unstructured":"M. Chrobak and G. Kant, Convex grid drawings of 3-connected planar graphs, Technical Report RUUCS-93\u201345, Department of Computer Science, Utrecht University, 1993."},{"key":"170300339_CR4","first-page":"104","volume-title":"Lecture Notes in Computer Science","author":"M. Chrobak","year":"1994","unstructured":"M. Chrobak and S. Nakano, Minimum-width grid drawings of planar graphs, Proc. Workshop on Graph Drawing, 1994, pp. 104\u2013110, Lecture Notes in Computer Science, Vol. 894, Springer-Verlag, Berlin."},{"key":"170300339_CR5","unstructured":"M. Chrobak and T. Payne, A linear time algorithm for drawing planar graphs on a grid, Technical Report UCR-CS-89\u20131, Department of Mathematics and Computer Science, University of California at Riverside, 1989."},{"key":"170300339_CR6","unstructured":"P. Eades and R. Tamassia, Algorithms for automatic graph drawing: an annotated bibliography, Technical Report, Department of Computer Science, Brown University, 1993."},{"key":"170300339_CR7","volume-title":"Graph Algorithms","author":"S. Even","year":"1979","unstructured":"S. Even, Graph Algorithms, Computer Science Press, Rockville, MD, 1979."},{"key":"170300339_CR8","first-page":"229","volume":"11","author":"F\u00e1ry I.","year":"1948","unstructured":"I. F\u00e1ry, On straight line representation of planar graphs, Acta. Sci. Math. (Szeged) 11 (1948), 229\u2013233.","journal-title":"Acta. Sci. Math. (Szeged)"},{"key":"170300339_CR9","doi-asserted-by":"crossref","unstructured":"H. de Fraysseix, J. Pach, and R. Pollack, Small sets supporting straight-line embeddings of planar graphs, Proc. 20th Annual ACM Symp. on Theory of Computing, 1988, pp. 426\u2013433.","DOI":"10.1145\/62212.62254"},{"key":"170300339_CR10","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF02122694","volume":"10","author":"H. Fraysseix de","year":"1990","unstructured":"H.de Fraysseix, J. Pach, and R. Pollack, How to draw a planar graph on a grid, Combinatorica 10 (1990), 41\u201351.","journal-title":"Combinatorica"},{"key":"170300339_CR11","doi-asserted-by":"crossref","unstructured":"M. F\u00fcrer, X. He, M. Y. Kao, and B. Raghavachari, O (n log log n)-work parallel algorithms for straight line grid embeddings of planar graphs, Proc. 4th Annual ACM Symp. on Parallel Algorithms and Architectures, 1992, pp. 410\u2013419. Complete version appeared in SJAMJ. Discrete Math. 7(4) (1994), 632\u2013646.","DOI":"10.1137\/S0895480191221453"},{"key":"170300339_CR12","first-page":"101","volume-title":"Drawing planar graphs using the lmc-ordering","author":"G. Kant","year":"1992","unstructured":"G. Kant, Drawing planar graphs using the lmc-ordering, Proc. 33th itAnnual IEEE Symp. on Foundations of Computer Science, Pittsburgh, 1992, pp. 101\u2013110."},{"key":"170300339_CR13","unstructured":"G. Kant, Algorithms for drawing planar graphs, Ph.D. Dissertation, Department of Computer Science, University of Utrecht, 1993."},{"key":"170300339_CR14","first-page":"396","volume-title":"Lecture Notes in Computer Science","author":"G. Kant","year":"1993","unstructured":"G. Kant and X. He, Two algorithms for finding rectangular duals of planar graphs, Proc. 19th Workshop on Graph-Theoretic Concepts in Computer Science, Utrecht, June 16\u201318, 1993, pp. 396\u2013410, Lecture Notes in Computer Science, Vol. 790, Springer-Verlag, Berlin. To appear in Theoretical Computer Science."},{"key":"170300339_CR15","doi-asserted-by":"crossref","unstructured":"F. P. Preparata and R. Tamassia, Fully dynamic techniques for point location and transitive closure in planar structures, Proc. 29th Annual IEEE Symp. on Foundations of Computer Science, 1988, pp. 558\u2013567.","DOI":"10.1109\/SFCS.1988.21972"},{"key":"170300339_CR16","first-page":"31","volume":"56","author":"R. C. Read","year":"1987","unstructured":"R. C. Read, A new method for drawing a planar graph given the cyclic order of the edges at each vertex, Congr. Numer. 56 (1987), 31\u201344.","journal-title":"Congr. Numer."},{"key":"170300339_CR17","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/BF02187706","volume":"1","author":"P. Rosenstiehl","year":"1986","unstructured":"P. Rosenstiehl and R. Tarjan, Rectilinear planar layouts and bipolar orientations of planar graphs, Discrete Comput. Geom. 1 (1986), 343\u2013353.","journal-title":"Discrete Comput. Geom."},{"key":"170300339_CR18","first-page":"268","volume":"9","author":"W. Schnyder","year":"1988","unstructured":"W. Schnyder, Embedding planar graphs on the grid, Abstracts Amer. Math. Soc. 9 (1988), 268.","journal-title":"Abstracts Amer. Math. Soc."},{"key":"170300339_CR19","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1007\/BF00353652","volume":"5","author":"W. Schnyder","year":"1989","unstructured":"W. Schnyder, Planar graphs and poset dimension. Orders 5 (1989), 323\u2013343.","journal-title":"Orders"},{"key":"170300339_CR20","unstructured":"W. Schnyder, Embedding planar graphs on the grid, Proc. 1st Annual ACM-SIAM Symp. on Discrete Algorithms, 1990, pp. 138\u2013147."},{"issue":"5","key":"170300339_CR21","first-page":"92","volume":"13","author":"W. Schnyder","year":"1992","unstructured":"W. Schnyder and W. Trotter, Convex drawings of planar graphs, Abstracts of Amer. Math. Soc. 13(5) (1992), 92\u2013135.","journal-title":"Abstracts of Amer. Math. Soc."},{"key":"170300339_CR22","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1090\/S0002-9939-1951-0041425-5","volume":"2","author":"S. K. Stein","year":"1951","unstructured":"S. K. Stein, Convex maps, Proc. Amer. Math. Soc. 2 (1951), 464\u2013466.","journal-title":"Proc. Amer. Math. Soc."},{"key":"170300339_CR23","doi-asserted-by":"crossref","first-page":"743","DOI":"10.1112\/plms\/s3-13.1.743","volume":"13","author":"W. T. Tutte","year":"1963","unstructured":"W. T. Tutte, How to draw a graph, Proc. London Math. Soc. 13 (1963), 743\u2013768.","journal-title":"Proc. London Math. Soc."},{"key":"170300339_CR24","first-page":"26","volume":"46","author":"K. Wagner","year":"1936","unstructured":"K. Wagner, Bemerkungen zum Vierfarben problem, Jahresber. Deutsch Math.-Verein. 46 (1936), 26\u201332. Received March 30, 1995, and in revised form January 3, 1996.","journal-title":"Jahresber. Deutsch Math.-Verein."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/PL00009290.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/PL00009290\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/PL00009290","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T09:20:46Z","timestamp":1558516846000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/PL00009290"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,4]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1997,4]]}},"alternative-id":["170300339"],"URL":"https:\/\/doi.org\/10.1007\/pl00009290","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,4]]}}}