{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T14:10:12Z","timestamp":1770732612226,"version":"3.49.0"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1996,7,1]],"date-time":"1996-07-01T00:00:00Z","timestamp":836179200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1996,7]]},"DOI":"10.1007\/bf02086606","type":"journal-article","created":{"date-parts":[[2005,8,15]],"date-time":"2005-08-15T00:28:41Z","timestamp":1124065721000},"page":"4-32","source":"Crossref","is-referenced-by-count":173,"title":["Drawing planar graphs using the canonical ordering"],"prefix":"10.1007","volume":"16","author":[{"given":"G.","family":"Kant","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02086606_CR1","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/BF01762117","volume":"3","author":"J. Bhasker","year":"1988","unstructured":"Bhasker, J., and S. Sahni, A linear algorithm to find a rectangular dual of a planar triangulated graph,Algorithmica 3 (1988), 147\u2013178.","journal-title":"Algorithmica"},{"key":"BF02086606_CR2","first-page":"24","volume-title":"Lecture Notes in Computer Science, Vol. 855","author":"T. Biedl","year":"1994","unstructured":"Biedl, T., and G. Kant, A better heuristic for planar orthogonal drawings, inProc. 2nd European Symp. on Algorithms (ESA '94), Lecture Notes in Computer Science, Vol. 855, Springer-Verlag, Berlin, 1994, pp. 24\u201336."},{"key":"BF02086606_CR3","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. S. Booth","year":"1976","unstructured":"Booth, K. S., and G. S. Lueker, Testing for the consecutive ones property, interval graphs and graph planarity testing using PQ-tree algorithms,J. Comput. System Sci. 13 (1976), 335\u2013379.","journal-title":"J. Comput. System Sci."},{"key":"BF02086606_CR4","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/0022-0000(85)90004-2","volume":"30","author":"N. Chiba","year":"1985","unstructured":"Chiba, N., T. Nishizeki, S. Abe, and T. Ozawa, A linear algorithm for embedding planar graphs using PQ-trees,J. Comput. System Sci. 30 (1985), 54\u201376.","journal-title":"J. Comput. System Sci."},{"key":"BF02086606_CR5","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/BF00264230","volume":"22","author":"N. Chiba","year":"1985","unstructured":"Chiba, N., K. Onoguchi, and T. Nishizeki, Drawing planar graphs nicely,Acta Inform. 22 (1985), 187\u2013201.","journal-title":"Acta Inform."},{"key":"BF02086606_CR6","unstructured":"Chrobak, M., and G. Kant, Convex Grid Drawings of 3-Connected Planar Graphs, Tech. Rep. RUU-CS-93-45, Dept. of Computer Science, Utrecht University, 1993."},{"key":"BF02086606_CR7","volume-title":"Tech. Rep. UCR-CS-90-2","author":"M. Chrobak","year":"1990","unstructured":"Chrobak, M., and T. H. Payne, A Linear Time Algorithm for Drawing Planar Graphs on the Grid, Tech. Rep. UCR-CS-90-2, Dept. of Mathematics and Computer Science, University of California at Riverside, 1990."},{"key":"BF02086606_CR8","doi-asserted-by":"crossref","unstructured":"Cohen, R. F., G. Di Battista, R. Tamassia, I. G. Tollis, and P. Bertolazzi, A framework for dynamic graph drawing, inProc. 8th Annual ACM Symp. on Computational Geometry, 1992, pp. 261\u2013270.","DOI":"10.1145\/142675.142728"},{"key":"BF02086606_CR9","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0925-7721(94)00014-X","volume":"4","author":"G. Battista Di","year":"1994","unstructured":"G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis, Algorithms for automatic graph drawing: an annotated bibliography,Comput. Geom. Theory Appl. 4 (1994), 235\u2013282.","journal-title":"Comput. Geom. Theory Appl."},{"key":"BF02086606_CR10","first-page":"151","volume-title":"Lecture Notes in Computer Science, Vol. 709","author":"G. Battista Di","year":"1993","unstructured":"Di Battista, G., G. Liotta, and F. Vargiu, Spirality of orthogonal representations and optimal drawings of series-parallel graphs and 3-planar graphs, inProc. Workshop on Algorithms and Data Structures (WADS '93), Lecture Notes in Computer Science, Vol. 709, Springer-Verlag, 1993, Berlin, pp. 151\u2013162."},{"key":"BF02086606_CR11","doi-asserted-by":"crossref","unstructured":"Di Battista, G., and R. Tamassia, Incremental planarity testing, inProc. 30th Annual IEEE Symp. on Foundations of Computer Science (FOCS '89), 1989, pp. 436\u2013441.","DOI":"10.1109\/SFCS.1989.63515"},{"key":"BF02086606_CR12","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/BF02187850","volume":"7","author":"G. Battista Di","year":"1992","unstructured":"Di Battista, G., R. Tamassia, and I. G. Tollis, Area requirement and symmetry display in drawing graphs,Discrete Comput. Geom. 7 (1992), 381\u2013401.","journal-title":"Discrete Comput. Geom."},{"key":"BF02086606_CR13","doi-asserted-by":"crossref","unstructured":"Di Battista, G., and L. Vismara, Angles of planar triangular graphs, extended abstract inProc. 25th Annual ACM Symp. on Theory of Computing, 1993, pp. 431\u2013437.","DOI":"10.1145\/167088.167207"},{"key":"BF02086606_CR14","volume-title":"Rectilinear Planar Drawings with Few Bends in Each Edge, Manuscript","author":"S. Even","year":"1993","unstructured":"Even, S., and G. Granot, Rectilinear Planar Drawings with Few Bends in Each Edge, Manuscript, Faculty of Computer Science, The Technion, Haifa, 1993."},{"key":"BF02086606_CR15","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1016\/0304-3975(76)90086-4","volume":"2","author":"S. Even","year":"1976","unstructured":"Even, S., and R. E. Tarjan, Computing anst-numbering,Theoret. Comp. Sci. 2 (1976), 436\u2013441.","journal-title":"Theoret. Comp. Sci."},{"key":"BF02086606_CR16","first-page":"229","volume":"11","author":"I. F\u00e1ry","year":"1948","unstructured":"F\u00e1ry, I., On straight line representations of planar graphs,Acta Sci. Math. Szeged,11 (1948), 229\u2013233.","journal-title":"Acta Sci. Math. Szeged"},{"key":"BF02086606_CR17","doi-asserted-by":"crossref","first-page":"1035","DOI":"10.1137\/0222063","volume":"22","author":"M. Formann","year":"1993","unstructured":"Formann, M., T. Hagerup, J. Haralambides, M. Kaufmann, F. T. Leighton, A. Simvonis, E. Welzl, and G. Woeginger, Drawing graphs in the plane with high resolution,SIAM J. Comput. 22 (1993), 1035\u20131052.","journal-title":"SIAM J. Comput."},{"key":"BF02086606_CR18","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF02122694","volume":"10","author":"H. Fraysseix de","year":"1990","unstructured":"Fraysseix, H. de, J. Fach, and R. Pollack, How to draw a planar graph on a grid,Combinatorica 10 (1990), 41\u201351.","journal-title":"Combinatorica"},{"key":"BF02086606_CR19","volume-title":"Lecture Notes in Computer Science","author":"A. Garg","year":"1994","unstructured":"Garg, A., and R. Tamassia, On the computational complexity of upward and rectilinear planarity testing, inProc. Graph Drawing '94, Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1994, to appear."},{"key":"BF02086606_CR20","first-page":"12","volume-title":"Lecture Notes in Computer Science, Vol. 855","author":"A. Garg","year":"1994","unstructured":"Garg, A., and R. Tamassia, Planar drawings and angular resolution: algorithms and bounds, inProc. 2nd European Symp. on Algorithms (ESA '94), Lecture Notes in Computer Science, Vol. 855, Springer-Verlag, Berlin, 1994, pp. 12\u201323."},{"key":"BF02086606_CR21","unstructured":"Haandel, F. van, Straight Line Embeddings on the Grid, M.Sc. Thesis, No. INF\/SCR-91-19, Dept. of Computer Science, Utrecht University, 1991."},{"key":"BF02086606_CR22","doi-asserted-by":"crossref","unstructured":"He, X., On finding the rectangular duals of planar triangulated graphs,SIAM J. Comput., 1993, to appear.","DOI":"10.1137\/0222072"},{"key":"BF02086606_CR23","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/3-540-57568-5_261","volume":"762","author":"X. He","year":"1993","unstructured":"He, X., and M.-Y. Kao, Parallel construction of canonical ordering and convex drawing of triconnected planar graphs, inProc. 4th Symp. on Algorithms and Computation (ISAAC '93), Lecture Notes in Computer Science, Vol. 762, 1993, pp. 303\u2013312.","journal-title":"Lecture Notes in Computer Science"},{"key":"BF02086606_CR24","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1137\/0202012","volume":"2","author":"J. Hopcroft","year":"1973","unstructured":"Hopcroft, J., and R. E. Tarjan, Dividing a graph into triconnected components,SIAM J. Comput. 2 (1973), 135\u2013158.","journal-title":"SIAM J. Comput."},{"key":"BF02086606_CR25","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"Hopcroft, J., and R. E. Tarjan, Efficient planarity testing,J. Assoc. Comput. Mach. 21 (1974), 549\u2013568.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02086606_CR26","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1109\/31.1746","volume":"35","author":"R. Jayakumar","year":"1988","unstructured":"Jayakumar, R., K. Thulasiraman, and M. N. S. Swamy, Planar embedding: linear-time algorithms for vertex placement and edge ordering,IEEE Trans. Circuits and Systems 35 (1988), 334\u2013344.","journal-title":"IEEE Trans. Circuits and Systems"},{"key":"BF02086606_CR27","first-page":"263","volume-title":"Lecture Notes in Computer Science, Vol. 657","author":"G. Kant","year":"1992","unstructured":"Kant, G., Hexagonal grid drawings, inProc. 18th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '92), Lecture Notes in Computer Science, Vol. 657, Springer-Verlag, Berlin, 1992, 263\u2013276."},{"key":"BF02086606_CR28","unstructured":"Kant, G., Algorithms for Drawing Planar Graphs, Ph.D. thesis, Dept. of Computer Science, Utrecht University, 1993."},{"key":"BF02086606_CR29","unstructured":"Kant, G., The planar triconnectivity augmentation problem, submitted toTheoret. Comput. Sci., 1993."},{"key":"BF02086606_CR30","first-page":"411","volume-title":"Lecture Notes in Computer Science, Vol. 790","author":"G. Kant","year":"1994","unstructured":"Kant, G., A more compact visibility representation, inProc. 19th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '93), Lecture Notes in Computer Science, Vol. 790, Springer-Verlag, Berlin, 1994, 411\u2013424."},{"key":"BF02086606_CR31","doi-asserted-by":"crossref","unstructured":"Kant, G., and X. He, Two algorithms for finding rectangular duals of planar graphs, inProc. 19th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '93), Lecture Notes in Computer Science, Vol. 790, Springer-Verlag, 1994, pp. 396\u2013410.","DOI":"10.1007\/3-540-57899-4_69"},{"key":"BF02086606_CR32","unstructured":"Lempel, A., S. Even, and I. Cederbaum, An algorithm for planarity testing of graphs,Theory of Graphs, International Symp., Rome, 1966, pp. 215\u2013232."},{"key":"BF02086606_CR33","unstructured":"Liu, Y., P. Marchioro, and R. Petreschi, At most single-bend embeddings of cubic graphs,Appl. Math., 1994, to appear."},{"key":"BF02086606_CR34","unstructured":"Liu, Y., P. Marchioro, R. Petreschi, and B. Simeone, Theoretical Results on at Most 1-Bend Embeddability of Graphs, Tech. Rep., Dept. of Statistics, University \u201cLa Sapienza\u201d Roma, 1990."},{"key":"BF02086606_CR35","volume-title":"Complexity Aspects of Visibility Graphs, Rep. 92-08","author":"Y.-L. Lin","year":"1992","unstructured":"Lin, Y.-L., and S. S. Skiena, Complexity Aspects of Visibility Graphs, Rep. 92-08, Dept. of Computer Science, State University of New York, Stony Brook, NY, 1992."},{"key":"BF02086606_CR36","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1137\/S0895480193242931","volume":"7","author":"S. Malitz","year":"1994","unstructured":"Malitz, S., and A. Papakostas, On the angular resolution of planar graphs,SIAM J. Discrete Math. 7 (1994), 172\u2013183.","journal-title":"SIAM J. Discrete Math."},{"key":"BF02086606_CR37","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0304-3975(92)90349-K","volume":"99","author":"J. Nummenmaa","year":"1992","unstructured":"Nummenmaa, J., Constructing compact rectilinear planar layouts using canonical representation of planar graphs,Theoret. Comput. Sci. 99 (1992), 213\u2013230.","journal-title":"Theoret. Comput. Sci."},{"key":"BF02086606_CR38","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/BF02187706","volume":"1","author":"P. Rosenstiehl","year":"1986","unstructured":"Rosenstiehl, P., and R. E. Tarjan, Rectilinear planar layouts and bipolar orientations of planar graphs,Discrete Comput. Geom. 1 (1986), 343\u2013353.","journal-title":"Discrete Comput. Geom."},{"key":"BF02086606_CR39","unstructured":"Schnyder, W., Embedding planar graphs on the grid, inProc. 1st Annual ACM-SIAM Symp. on Discrete Algebra (SODA '90), 1990, pp. 138\u2013147."},{"key":"BF02086606_CR40","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1090\/S0002-9939-1951-0041425-5","volume":"2","author":"S. K. Stein","year":"1951","unstructured":"Stein, S. K., Convex maps,Proc. Amer. Math. Soc. 2 (1951), 464\u2013466.","journal-title":"Proc. Amer. Math. Soc."},{"key":"BF02086606_CR41","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1002\/net.3230140202","volume":"14","author":"J. A. Storer","year":"1984","unstructured":"Storer, J. A., On minimal node-cost planar embeddings,Networks 14 (1984), 181\u2013212.","journal-title":"Networks"},{"key":"BF02086606_CR42","doi-asserted-by":"crossref","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. 16 (1987), 421\u2013444.","journal-title":"SIAM J. Comput."},{"key":"BF02086606_CR43","doi-asserted-by":"crossref","first-page":"1230","DOI":"10.1109\/31.34669","volume":"36","author":"R. Tamassia","year":"1989","unstructured":"Tamassia, R., and I. G. Tollis, Planar grid embedding in linear time,IEEE Trans. Circuits and Systems,36 (1989), 1230\u20131234.","journal-title":"IEEE Trans. Circuits and Systems"},{"key":"BF02086606_CR44","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/BF02187705","volume":"1","author":"R. Tamassia","year":"1986","unstructured":"Tamassia, R., and I. G. Tollis, A unified approach to visibility representations of planar graphs,Discrete and Comput. Geom. 1 (1986), 321\u2013341.","journal-title":"Discrete and Comput. Geom."},{"key":"BF02086606_CR45","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0020-0190(91)90059-Q","volume":"39","author":"R. Tamassia","year":"1991","unstructured":"Tamassia, R., I. G. Tollis, and J. S. Vitter, Lower bounds for planar orthogonal drawings of graphs,Inform. Process. Lett. 39 (1991), 35\u201340.","journal-title":"Inform. Process. Lett."},{"key":"BF02086606_CR46","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/0095-8956(80)90083-0","volume":"29","author":"C. Thomassen","year":"1980","unstructured":"Thomassen, C., Planarity and duality of finite and infinite planar graphs,J. Combin. Theory Ser. B 29 (1980), 244\u2013271.","journal-title":"J. Combin. Theory Ser. B"},{"key":"BF02086606_CR47","first-page":"302","volume":"10","author":"W. T. Tutte","year":"1960","unstructured":"Tutte, W. T., Convex representations of graphs,Proc. London Math. Soc. 10 (1960), 302\u2013320.","journal-title":"Proc. London Math. Soc."},{"key":"BF02086606_CR48","doi-asserted-by":"crossref","first-page":"743","DOI":"10.1112\/plms\/s3-13.1.743","volume":"13","author":"W. T. Tutte","year":"1963","unstructured":"Tutte, W. T., How to draw a graph,Proc. London Math. Soc. 13 (1963), 743\u2013768.","journal-title":"Proc. London Math. Soc."},{"key":"BF02086606_CR49","first-page":"26","volume":"46","author":"K. Wagner","year":"1936","unstructured":"Wagner, K., Bemerkungen zum vierfarbenproblem,Jahresber. Deutsch. Math.-Verein. 46 (1936), 26\u201332.","journal-title":"Jahresber. Deutsch. Math.-Verein."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02086606.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02086606\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02086606","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,9]],"date-time":"2020-04-09T01:17:43Z","timestamp":1586395063000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02086606"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,7]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1996,7]]}},"alternative-id":["BF02086606"],"URL":"https:\/\/doi.org\/10.1007\/bf02086606","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,7]]}}}