{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:08:00Z","timestamp":1725664080128},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540589501"},{"type":"electronic","value":"9783540491552"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-58950-3_360","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:53:54Z","timestamp":1330257234000},"page":"96-103","source":"Crossref","is-referenced-by-count":3,"title":["Regular edge labelings and drawings of planar graphs"],"prefix":"10.1007","author":[{"given":"Xin","family":"He","sequence":"first","affiliation":[]},{"given":"Ming-Yang","family":"Kao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1002\/net.3230170306","volume":"17","author":"J. Bhasker","year":"1987","unstructured":"J. Bhasker and S. Sahni, A linear algorithm to check for the existence of a rectangular dual of a planar triangulated graph, Networks 17, 1987, pp. 307\u2013317.","journal-title":"Networks"},{"key":"10_CR2","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/BF01762117","volume":"3","author":"J. Bhasker","year":"1988","unstructured":"J. Bhasker and S. Sahni, A linear algorithm to find a rectangular dual of a planar triangulated graph, Algorithmica 3, 1988, pp. 247\u2013278.","journal-title":"Algorithmica"},{"key":"10_CR3","unstructured":"N. Chiba, T. Yamanouchi, and T. Nishizeki, Linear algorithms for convex drawings of planar graphs, in Progress in Graph Theory, 1982, pp. 153\u2013173."},{"key":"10_CR4","unstructured":"M. Chrobak and T. H. Payne, A linear time algorithm for drawing planar graphs on a grid, TR. UCR-CS-90-2, Dept. of Math. and CS., Univ. of Calif. at Riverside."},{"key":"10_CR5","unstructured":"P. Eades and R. Tamassia, Algorithms for automatic graph drawing: an annotated bibliography, TR., Dept. of Comp. Sci., Brown Univ., 1993."},{"key":"10_CR6","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), pp. 41\u201351.","journal-title":"Combinatorica"},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"H. de Fraysseix, J. Pach and R. Pollack, Small sets supporting F\u00e1ry embeddings of planar graphs, Proc. of the 20th ACM STOC, 1988, pp. 426\u2013433.","DOI":"10.1145\/62212.62254"},{"key":"10_CR8","first-page":"229","volume":"11","author":"I. F\u00e1ry","year":"1948","unstructured":"I. F\u00e1ry, On straight line representation of planar graphs, Acta Sci Math Szeged, 11 (1948), pp. 229\u2013233.","journal-title":"Acta Sci Math Szeged"},{"key":"10_CR9","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. of 4th ACM SPAA, 1992, pp. 410\u2013419. Improved version to appear in SIAM J. Discrete Math.","DOI":"10.1145\/140901.141933"},{"issue":"6","key":"10_CR10","doi-asserted-by":"crossref","first-page":"1218","DOI":"10.1137\/0222072","volume":"22","author":"X. He","year":"1993","unstructured":"X. He, On finding the rectangular duals of planar triangulated graphs, SIAM J. Comput. 22 (6), 1993, pp. 1218\u20131226.","journal-title":"SIAM J. Comput"},{"key":"10_CR11","unstructured":"X. He, An efficient parallel algorithm for finding rectangular duals of planar triangular graphs, Proc. 3rd International Conference for Young Computer Scientists, Beijing, 1993, pp. 6.33\u20136.37. Complete version to appear in Algorithmica."},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"W. R. Heller, G. Sorkin and K. Mailing, The planar package planner for system designers, Proc. 19th IEEE Design Automation Conf., 1982, pp. 253\u2013260.","DOI":"10.1109\/DAC.1982.1585509"},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"G. Kant, Drawing planar graphs using the lmc-ordering, in Proc. 33th Ann. IEEE Symp. on Found. of Comp. Science, Pittsburgh, 1992, pp. 101\u2013110.","DOI":"10.1109\/SFCS.1992.267814"},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"G. Kant, A more compact visibility representation, in: J. van Leeuwen (Ed.), Proc. 19th Intern. Workshop on Graph-Theoretic Concepts in Comp. Science (WG'93).","DOI":"10.1007\/3-540-57899-4_70"},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"G. Kant and X. He, Two algorithms for finding rectangular duals of planar graphs, in: J. van Leeuwen (Ed.), Proc. 19th Intern. Workshop on Graph-Theoretic Concepts in Comp. Science (WG'93), LNCS, Springer-Verlag, 1994, to appear.","DOI":"10.1007\/3-540-57899-4_69"},{"key":"10_CR16","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1002\/net.3230150202","volume":"15","author":"K. Ko\u017ami\u0144ski","year":"1985","unstructured":"K. Ko\u017ami\u0144ski and E. Kinnen, Rectangular dual of planar graphs, Networks 15, 1985, pp. 145\u2013157.","journal-title":"Networks"},{"key":"10_CR17","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/BF01840399","volume":"5","author":"Y.-T. Lai","year":"1990","unstructured":"Y.-T. Lai and S. M. Leinwand, A theory of rectangular dual graphs, Algorithmica 5, 1990, pp. 467\u2013483.","journal-title":"Algorithmica"},{"key":"10_CR18","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 FOCS, 1988, pp. 558\u2013567.","DOI":"10.1109\/SFCS.1988.21972"},{"key":"10_CR19","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, Congressus Numerantium 56 (1987), pp. 31\u201344.","journal-title":"Congressus Numerantium"},{"key":"10_CR20","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/BF02187706","volume":"1","author":"P. Rosenstiehl","year":"1986","unstructured":"P. Rosenstiehl and R. E. Tarjan, Rectilinear planar layouts and bipolar orientations of planar graphs, Discr. and Comp. Geometry 1, 1986, pp. 343\u2013353.","journal-title":"Discr. and Comp. Geometry"},{"key":"10_CR21","first-page":"268","volume":"9","author":"W. Schnyder","year":"1988","unstructured":"W. Schnyder, Embedding planar graphs on the grid, Abstracts of the Amer. Math. Soc., 9 (1988), p. 268.","journal-title":"Abstracts of the Amer. Math. Soc."},{"key":"10_CR22","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), pp. 323\u2013343.","journal-title":"Orders"},{"key":"10_CR23","unstructured":"W. Schnyder, Embedding planar graphs on the grid, in Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, 1990, pp. 138\u2013148."},{"key":"10_CR24","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, in Proc Amer Math Soc, vol. 2, 1951, pp. 464\u2013466.","journal-title":"Proc Amer Math Soc"},{"issue":"2","key":"10_CR25","doi-asserted-by":"crossref","first-page":"708","DOI":"10.1137\/0220045","volume":"20","author":"R. Tamassia","year":"1991","unstructured":"R. Tamassia and J. S. Vitter, Parallel transitive closure and point location in planar structures, SIAM J. Comput. 20 (2), 1991, pp. 708\u2013725.","journal-title":"SIAM J. Comput."},{"key":"10_CR26","first-page":"217","volume":"2","author":"R. Tamassia","year":"1990","unstructured":"R. Tamassia, Drawing Algorithms for Planar s-t Graphs, Australasian Journal of Combinatorics, Vol. 2, 1990, pp. 217\u2013236.","journal-title":"Australasian Journal of Combinatorics"},{"key":"10_CR27","unstructured":"R. Tamassia and I. Tollis, Tessellation Representations of Planar Graphs, in Proc. 27th Allerton Conference, 1989, pp. 48\u201357."},{"key":"10_CR28","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/BF02187705","volume":"1","author":"R. Tamassia","year":"1986","unstructured":"R. Tamassia and I. G. Tollis, A unified approach to visibility representations of planar graphs, Discr. and Comp. Geometry 1, 1986, pp. 321\u2013341.","journal-title":"Discr. and Comp. Geometry"},{"key":"10_CR29","doi-asserted-by":"crossref","first-page":"1230","DOI":"10.1109\/31.34669","volume":"36","author":"R. Tamassia","year":"1989","unstructured":"R. Tamassia and I. G. Tollis, Planar grid embedding in linear time, IEEE Trans. Circuits and Systems 36, 1989, pp. 1230\u20131234.","journal-title":"IEEE Trans. Circuits and Systems"},{"key":"10_CR30","doi-asserted-by":"crossref","first-page":"743","DOI":"10.1112\/plms\/s3-13.1.743","volume":"13","author":"W. Tutte","year":"1963","unstructured":"W. Tutte, How to draw a graph, Proc. London Math. Soc. 13, 1963, pp. 743\u2013768.","journal-title":"Proc. London Math. Soc."},{"key":"10_CR31","first-page":"26","volume":"46","author":"K. Wagner","year":"1936","unstructured":"K. Wagner, Bemerkungen zum Vierfarbenproblem, Jahresbericht Deutsch Math-Verein, 46 (1936), pp. 26\u201332.","journal-title":"Jahresbericht Deutsch Math-Verein"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58950-3_360.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:24:48Z","timestamp":1605630288000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58950-3_360"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540589501","9783540491552"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/3-540-58950-3_360","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}