{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T14:58:38Z","timestamp":1725893918065},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540778905"},{"type":"electronic","value":"9783540778912"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77891-2_12","type":"book-chapter","created":{"date-parts":[[2008,1,12]],"date-time":"2008-01-12T08:19:36Z","timestamp":1200125976000},"page":"120-131","source":"Crossref","is-referenced-by-count":2,"title":["A Compact Encoding of Plane Triangulations with Efficient Query Supports"],"prefix":"10.1007","author":[{"given":"Katsuhisa","family":"Yamanaka","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shin-ichi","family":"Nakano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1007\/11534273_13","volume-title":"Algorithms and Data Structures","author":"L.C. Aleardi","year":"2005","unstructured":"Aleardi, L.C., Devillers, O., Schaeffer, G.: Succinct representation of triangulations with a boundary. In: Dehne, F., L\u00f3pez-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol.\u00a03608, pp. 134\u2013145. Springer, Heidelberg (2005)"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Aleardi, L.C., Devillers, O., Schaeffer, G.: Optimal Succinct Representations of Planar Maps. In: Proc. of SCG 2006, pp. 309\u2013318 (2006)","DOI":"10.1145\/1137856.1137902"},{"key":"12_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1007\/3-540-36494-3_44","volume-title":"STACS 2003","author":"N. Bonichon","year":"2003","unstructured":"Bonichon, N., Gavoille, C., Hanusse, N.: An Information-Theoretic Upper Bound of Planar Graphs Using Triangulation. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol.\u00a02607, pp. 499\u2013510. Springer, Heidelberg (2003)"},{"key":"12_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/BFb0055046","volume-title":"Automata, Languages and Programming","author":"R.C.N. Chuang","year":"1998","unstructured":"Chuang, R.C.N., Garg, A., He, X., Kao, M.Y., Lu, H.I.: Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol.\u00a01443, pp. 118\u2013129. Springer, Heidelberg (1998)"},{"key":"12_CR5","unstructured":"Chiang, Y.T., Lin, C.C., Lu, H.I.: Orderly Spanning Trees with Applications to Graph Encoding and Graph Drawing. In: Proc. of 12th SODA, pp. 506\u2013515 (2001)"},{"key":"12_CR6","doi-asserted-by":"publisher","first-page":"924","DOI":"10.1137\/S0097539702411381","volume":"34","author":"Y.T. Chiang","year":"2005","unstructured":"Chiang, Y.T., Lin, C.C., Lu, H.I.: Orderly Spanning Trees with Applications. SIAM J. Comput.\u00a034, 924\u2013945 (2005)","journal-title":"SIAM J. Comput."},{"key":"12_CR7","unstructured":"Clark, D.R.: Compact Pat Trees, PhD thesis, University of Waterloo (1998)"},{"key":"12_CR8","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/S0895480197325031","volume":"12","author":"X. He","year":"1999","unstructured":"He, X., Kao, M.Y., Lu, H.I.: Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings. SIAM J. Discrete Math.\u00a012, 317\u2013325 (1999)","journal-title":"SIAM J. Discrete Math."},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1137\/S0097539799359117","volume":"30","author":"X. He","year":"2000","unstructured":"He, X., Kao, M.Y., Lu, H.I.: A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs. SIAM J. Comput.\u00a030, 838\u2013846 (2000)","journal-title":"SIAM J. Comput."},{"key":"12_CR10","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient Static Trees and Graphs. In: Proc. of 30th FOCS, pp. 549\u2013554 (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"key":"12_CR11","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0166-218X(93)E0150-W","volume":"58","author":"K. Keeler","year":"1995","unstructured":"Keeler, K., Westbrook, J.: Short Encodings of Planar Graphs and Maps. Discrete Appl. Math.\u00a058, 239\u2013252 (1995)","journal-title":"Discrete Appl. Math."},{"key":"12_CR12","doi-asserted-by":"crossref","unstructured":"Lu, H.I., Yeh, C.C.: Balanced Parentheses Strike Back. ACM Transactions on Algorithms (to appear)","DOI":"10.1145\/1367064.1367068"},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"Munro, J.I., Raman, V.: Succinct Representation of Balanced Parentheses, Static Trees and Planar graphs. In: Proc. of 38th FOCS, pp. 118\u2013126 (1997)","DOI":"10.1109\/SFCS.1997.646100"},{"key":"12_CR14","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/S0097539799364092","volume":"31","author":"J.I. Munro","year":"2001","unstructured":"Munro, J.I., Raman, V.: Succinct Representation of Balanced Parentheses and Static Trees. SIAM J. Comput.\u00a031, 762\u2013776 (2001)","journal-title":"SIAM J. Comput."},{"key":"12_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1080","DOI":"10.1007\/3-540-45061-0_83","volume-title":"Automata, Languages and Programming","author":"D. Poulalhon","year":"2003","unstructured":"Poulalhon, D., Schaeffer, G.: Optimal Coding and Sampling of Triangulations. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 1080\u20131094. Springer, Heidelberg (2003)"},{"volume-title":"Handbook of Discrete and Combinatorial Mathematics","year":"2000","key":"12_CR16","unstructured":"Rosen, K.H. (eds.): Handbook of Discrete and Combinatorial Mathematics. CRC Press, Boca Raton (2000)"},{"key":"12_CR17","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1109\/2945.764870","volume":"5","author":"J. Rossignac","year":"1999","unstructured":"Rossignac, J.: Edgebreaker: Connectivity compression for triangle meshes. IEEE Trans. on Visualization and Computer Graphics\u00a05, 47\u201361 (1999)","journal-title":"IEEE Trans. on Visualization and Computer Graphics"},{"key":"12_CR18","unstructured":"Schnyder, W.: Embedding Planar Graphs in the Grid. In: Proc. of 1st SODA, pp. 138\u2013147 (1990)"},{"key":"12_CR19","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0166-218X(84)90126-4","volume":"8","author":"G. Turan","year":"1984","unstructured":"Turan, G.: Succinct Representations of Graphs. Discrete Appl. Math.\u00a08, 289\u2013294 (1984)","journal-title":"Discrete Appl. Math."},{"key":"12_CR20","doi-asserted-by":"crossref","first-page":"21","DOI":"10.4153\/CJM-1962-002-9","volume":"14","author":"W. Tutte","year":"1962","unstructured":"Tutte, W.: A Census of Planar Triangulations. Canad. J. Math.\u00a014, 21\u201338 (1962)","journal-title":"Canad. J. Math."}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77891-2_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:55:03Z","timestamp":1619520903000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77891-2_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540778905","9783540778912"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77891-2_12","relation":{},"subject":[]}}