{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:44:23Z","timestamp":1787507063994,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540647812","type":"print"},{"value":"9783540686811","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0055046","type":"book-chapter","created":{"date-parts":[[2006,8,1]],"date-time":"2006-08-01T08:08:05Z","timestamp":1154419685000},"page":"118-129","source":"Crossref","is-referenced-by-count":46,"title":["Compact encodings of planar graphs via canonical orderings and multiple parentheses"],"prefix":"10.1007","author":[{"given":"Richie Chih-Nan","family":"Chuang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ashim","family":"Garg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xin","family":"He","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ming-Yang","family":"Kao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hsueh-I","family":"Lu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2006,5,26]]},"reference":[{"key":"11_CR1","unstructured":"T. Bell, J. G. Cleary, and I. Witten, Text Compression, Prentice-Hall, 1990."},{"key":"11_CR2","unstructured":"D. R. Clark, Compact Pat Tree, PhD thesis, University of Waterloo, 1996."},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF02122694","volume":"10","author":"H. D. Fraysseix","year":"1990","unstructured":"H. D. 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":"11_CR4","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/S0019-9958(83)80004-7","volume":"56","author":"H. Galperin","year":"1983","unstructured":"H. Galperin and A. Wigderson, Succinct representations of graphs, Information and Control, 56 (1983), pp. 183\u2013198.","journal-title":"Information and Control"},{"key":"11_CR5","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF00288971","volume":"17","author":"A. Itai","year":"1982","unstructured":"A. Itai and M. Rodeh, Representation of graphs, Acta Informatica, 17 (1982), pp. 215\u2013219.","journal-title":"Acta Informatica"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"G. Jacobson, Space-efficient static trees and graphs, in proc. 30th FOCS, 30 Oct.\u20131 Nov. 1989, pp. 549\u2013554.","DOI":"10.1109\/SFCS.1989.63533"},{"key":"11_CR7","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1137\/0405049","volume":"5","author":"S. Kannan","year":"1992","unstructured":"S. Kannan, N. Naor, and S. Rudich, Implicit representation of graphs, SIAM Journal on Discrete Mathematics, 5 (1992), pp. 596\u2013603.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"G. Kant, Drawing planar graphs using the lmc-ordering (extended abstract), in proc. 33rd FOCS, 24\u201327 Oct. 1992, pp. 101\u2013110.","DOI":"10.1109\/SFCS.1992.267814"},{"key":"11_CR9","unstructured":"-, Algorithms for Drawing Planar Graphs, PhD thesis, Univ. of Utrecht, 1993."},{"key":"11_CR10","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/S0304-3975(95)00257-X","volume":"172","author":"G. Kant","year":"1997","unstructured":"G. Kant and X. He, Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems, TCS 172 (1997), pp. 175\u2013193.","journal-title":"TCS"},{"key":"11_CR11","doi-asserted-by":"publisher","first-page":"632","DOI":"10.1137\/S0895480191221453","volume":"7","author":"M. Y. Kao","year":"1994","unstructured":"M. Y. Kao, M. F\u00fcrer, X. He, and B. Raghavachari, Optimal parallel algorithms for straight-line grid embeddings of planar graphs, SIAM Journal on Discrete Mathematics, 7 (1994), pp. 632\u2013646.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"11_CR12","first-page":"201","volume-title":"LNCS 834","author":"M. Y. Kao","year":"1994","unstructured":"M. Y. Kao and S. H. Teng, Simple and efficient compression schemes for dense and complement graphs, in Fifth Annual Symposium on Algorithms and Computation, LNCS 834, Beijing, China, 1994, Springer-Verlag, pp. 201\u2013210."},{"key":"11_CR13","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0166-218X(93)E0150-W","volume":"58","author":"K. Keeler","year":"1995","unstructured":"K. Keeler and J. Westbrook, Short encodings of planar graphs and maps, Discrete Applied Mathematics, 58 (1995), pp. 239\u2013252.","journal-title":"Discrete Applied Mathematics"},{"key":"11_CR14","doi-asserted-by":"crossref","unstructured":"J. I. Munro, Tables, in proc. of 16th Conf. on Foundations of Software Technology and Theoret. Comp. Sci., LNCS 1180, 1996, Springer-Verlag, pp. 37\u201342.","DOI":"10.1007\/3-540-62034-6_35"},{"key":"11_CR15","unstructured":"J. I. Munro and V. Raman, Succinct representation of balanced parentheses, static trees and planar graphs, in proc. 38th FOCS 20\u201322 Oct. 1997."},{"key":"11_CR16","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0166-218X(90)90011-Z","volume":"28","author":"M. Naor","year":"1990","unstructured":"M. Naor, Succinct representation of general unlabeled graphs, Discrete Applied Mathematics, 28 (1990), pp. 303\u2013307.","journal-title":"Discrete Applied Mathematics"},{"key":"11_CR17","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0019-9958(86)80009-2","volume":"71","author":"C. H. Papadimitriou","year":"1986","unstructured":"C. H. Papadimitriou and M. Yannakakis, A note on succinct representations of graphs, Information and Control, 71 (1986), pp. 181\u2013185.","journal-title":"Information and Control"},{"key":"11_CR18","unstructured":"W. Schnyder, Embedding planar graphs on the grid, in Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990, pp. 138\u2013148."},{"key":"11_CR19","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0166-218X(84)90126-4","volume":"8","author":"G. Tur\u00e1n","year":"1984","unstructured":"G. Tur\u00e1n, On the succinct representation of graphs, Discrete Applied Mathematics, 8 (1984), pp. 289\u2013294.","journal-title":"Discrete Applied Mathematics"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0055046","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,20]],"date-time":"2019-04-20T08:19:12Z","timestamp":1555748352000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0055046"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540647812","9783540686811"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/bfb0055046","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998]]}}}