{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:22:59Z","timestamp":1759638179288},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540006237"},{"type":"electronic","value":"9783540364948"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-36494-3_44","type":"book-chapter","created":{"date-parts":[[2010,3,29]],"date-time":"2010-03-29T17:12:04Z","timestamp":1269882724000},"page":"499-510","source":"Crossref","is-referenced-by-count":21,"title":["An Information-Theoretic Upper Bound of Planar Graphs Using Triangulation"],"prefix":"10.1007","author":[{"given":"Nicolas","family":"Bonichon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cyril","family":"Gavoille","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicolas","family":"Hanusse","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,2,17]]},"reference":[{"issue":"2","key":"44_CR1","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/BF02522824","volume":"17","author":"L. Alonso","year":"1997","unstructured":"L. Alonso, J. L. R\u00e9my, and R. Schott. A linear-time algorithm for the generation of trees. Algorithmica, 17(2):162\u2013182, 1997.","journal-title":"Algorithmica"},{"key":"44_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1007\/3-540-45022-X_33","volume-title":"27th ICALP","author":"C. Banderier","year":"2000","unstructured":"C. Banderier, P. Flajolet, G. Schaeffer, and M. Soria. Planar maps and airy phenomena.In 27th ICALP, vol. 1853 of LNCS, pp. 388\u2013402. Springer, Jul. 2000."},{"issue":"2","key":"44_CR3","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/S0304-3975(98)00322-3","volume":"218","author":"E. Barcucci","year":"1999","unstructured":"E. Barcucci, A. del Lungo, and E. Pergola. Random generation of trees and other combinatorial objects. Theoretical Computer Science, 218(2):219\u2013232, 1999.","journal-title":"Theoretical Computer Science"},{"key":"44_CR4","unstructured":"E.A. Bender, Z. Gao, and N.C. Wormald. The number of labeled 2-connected planar graphs, 1999. Manuscript."},{"key":"44_CR5","unstructured":"M. Bodirsky and M. Kang. Generating random outerplanar graphs. In ALICE\u2019 03."},{"key":"44_CR6","volume-title":"Extremal Graph Theory","author":"B. Bollob\u00e1s","year":"1978","unstructured":"B. Bollob\u00e1s. Extremal Graph Theory. Academic Press, New York, 1978."},{"key":"44_CR7","unstructured":"N. Bonichon. A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths. In FPSAC, Jul. 2002."},{"key":"44_CR8","doi-asserted-by":"crossref","unstructured":"N. Bonichon, C. Gavoille, and N. Hanusse. An information upper bound of planar graphs using triangulation. TR #1279-02, LaBRI, Univ. of Bordeaux, Sep. 2002.","DOI":"10.1007\/3-540-36494-3_44"},{"key":"44_CR9","unstructured":"M. Bousquet-M\u00e9lou, 2002. Private communication."},{"key":"44_CR10","unstructured":"Y.-T. Chiang, C.-C. Lin, and H.-I Lu. Orderly spanning trees with applications to graph encoding and graph drawing. In 12th SODA, pp. 506\u2013515, Jan. 2001."},{"issue":"1","key":"44_CR11","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/0022-0000(85)90004-2","volume":"30","author":"N. Chiba","year":"1985","unstructured":"N. Chiba, T. Nishizeki, S. Abe, and T. Ozawa. A linear algorithm for embedding planar graphs using pq-trees. J. of Comp. and Sys. Sci., 30(1):54\u201376, 1985.","journal-title":"J. of Comp. and Sys. Sci."},{"key":"44_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1007\/BFb0055046","volume-title":"25th ICALP","author":"R.C.-N. Chuang","year":"1998","unstructured":"R.C.-N. Chuang, A. Garg, X. He, M.-Y. Kao, and H.-I Lu. Compact encodings of planar graphs via canonical orderings and multiple parentheses. In 25th ICALP, vol. 1443 of LNCS, pp. 118\u2013129. Springer, Jul. 1998."},{"key":"44_CR13","first-page":"61","volume":"113","author":"A. Denise","year":"1996","unstructured":"A. Denise, M. Vasconcellos, and D.J.A. Welsh. The random planar graph. Congressus Numerantium, 113:61\u201379, 1996.","journal-title":"Congressus Numerantium"},{"key":"44_CR14","doi-asserted-by":"crossref","unstructured":"R. Diestel. Graph Theory, vol. 173 of Graduate Texts in Math. Springer, 2000.","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"44_CR15","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1145\/189443.189446","volume":"4","author":"P. Epstein","year":"1994","unstructured":"P. Epstein and J.-R. Sack. Generating triangulations at random. ACM Trans. Model. and Comput. Simul.,4:267\u2013278, 1994.","journal-title":"ACM Trans. Model. and Comput. Simul"},{"issue":"4","key":"44_CR16","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1137\/0218058","volume":"18","author":"G.N. Frederickson","year":"1989","unstructured":"G.N. Frederickson and R. Janardan. Efficient message routing in planar networks. SIAM J. on Computing, 18(4):843\u2013857, August 1989.","journal-title":"SIAM J. on Computing"},{"key":"44_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/3-540-48523-6_32","volume-title":"26th ICALP","author":"C. Gavoille","year":"1999","unstructured":"C. Gavoille and N. Hanusse. Compact routing tables for graphs of bounded genus. In 26th ICALP, vol. 1644 of LNCS, pp. 351\u2013360. Springer, Jul. 1999."},{"key":"44_CR18","unstructured":"S. Gerke and C. McDiarmid. Adding edges to planar graphs, 2001. Preprint."},{"key":"44_CR19","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1137\/S0097539799359117","volume":"30","author":"X. He","year":"2000","unstructured":"X. He, M.-Y. Kao, and H.-I Lu. A fast general methodology for informationtheoretically optimal encodings of graphs. SIAM J. on Comp., 30:838\u2013846, 2000.","journal-title":"SIAM J. on Comp."},{"key":"44_CR20","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. Discr. Appl. Math., 58:239\u2013252, 1995.","journal-title":"Discr. Appl. Math."},{"key":"44_CR21","doi-asserted-by":"crossref","unstructured":"A. Khodakovsky, P. Alliez, M. Desbrun, and P. Schr\u00f6der. Near-optimal connectivity encoding of 2-manifold polygon meshes. Graphical Models, 2002. To appear.","DOI":"10.1006\/gmod.2002.0575"},{"key":"44_CR22","unstructured":"D. King and J. Rossignac. Guaranteed 3.67V bit encoding of planar triangle graphs. In 11th CCCG, pp. 146\u2013149, Aug. 1999."},{"key":"44_CR23","first-page":"97","volume":"34","author":"Y. Liu","year":"1988","unstructured":"Y. Liu. Enumeration of simple planar maps. Util. Math., 34:97\u2013104, 1988.","journal-title":"Util. Math."},{"issue":"2","key":"44_CR24","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"R.J. Lipton and R.E. Tarjan. A separator theorem for planar graphs. SIAM J. on Applied Mathematics, 36(2):177\u2013189, Apr. 1979.","journal-title":"SIAM J. on Applied Mathematics"},{"key":"44_CR25","first-page":"269","volume":"60","author":"V.A. Liskovets","year":"1987","unstructured":"V.A. Liskovets and T.R. Walsh. Ten steps to counting planar graphs. Congressus Numerantium, 60:269\u2013277, 1987.","journal-title":"Congressus Numerantium"},{"key":"44_CR26","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/3-540-45655-4_8","volume-title":"8th COCOON","author":"H.-I. Lu","year":"2002","unstructured":"H.-I Lu. Improved compact routing tables for planar networks via orderly spanning trees. In 8th COCOON, vol. 2387 of LNCS, pp. 57\u201366. Springer, Aug. 2002."},{"key":"44_CR27","unstructured":"H.-I Lu. Linear-time compression of bounded-genus graphs into informationtheoretically optimal number of bits. In 13th SODA, pp. 223\u2013224, Jan. 2002."},{"key":"44_CR28","doi-asserted-by":"crossref","unstructured":"J.I. Munro and V. Raman. Succinct representation of balanced parentheses, static trees and planar graphs. In 38th FOCS, pp. 118\u2013126. IEEE Press, 1997.","DOI":"10.1109\/SFCS.1997.646100"},{"key":"44_CR29","doi-asserted-by":"crossref","unstructured":"D. Osthus, H.J. Pr\u00f6mel, and A. Taraz. On random planar graphs, the number of planar graphs and their triangulations. Submitted for publication, 2002.","DOI":"10.1016\/S0095-8956(02)00040-0"},{"issue":"2","key":"44_CR30","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1137\/S0097539700369909","volume":"31","author":"R. Pagh","year":"2001","unstructured":"R. Pagh. Low redundancy in static dictionaries with constant query time. SIAM J. on Computing, 31(2):353\u2013363, 2001.","journal-title":"SIAM J. on Computing"},{"issue":"1","key":"44_CR31","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1109\/2945.764870","volume":"5","author":"J. Rossignac","year":"1999","unstructured":"J. Rossignac. Edgebreaker: Connectivity compression for triangle meshes. IEEE Transactions on Visualization and Computer Graphics, 5(1):47\u201361, 1999.","journal-title":"IEEE Transactions on Visualization and Computer Graphics"},{"key":"44_CR32","doi-asserted-by":"crossref","unstructured":"G. Schaeffer. Random sampling of large planar maps and convex polyhedra. In 31st STOC, pp. 760\u2013769, May 1999.","DOI":"10.1145\/301250.301448"},{"key":"44_CR33","unstructured":"W. Schnyder. Embedding planar graphs on the grid. In SODA\u2019 90, pp. 138\u2013148."},{"key":"44_CR34","doi-asserted-by":"crossref","unstructured":"M. Thorup. Compact oracles for reachability and approximate distances in planar digraphs. In 42th FOCS. IEEE Computer Society Press, Oct. 2001.","DOI":"10.1109\/SFCS.2001.959898"},{"key":"44_CR35","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. Succinct representations of graphs. Discr. Appl. Math., 8:289\u2013294, 1984.","journal-title":"Discr. Appl. Math."},{"key":"44_CR36","doi-asserted-by":"crossref","first-page":"21","DOI":"10.4153\/CJM-1962-002-9","volume":"14","author":"W.T. Tutte","year":"1962","unstructured":"W.T. Tutte. A census of planar triangulations. Can. J. of Math., 14:21\u201338, 1962.","journal-title":"Can. J. of Math."},{"key":"44_CR37","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/0022-0000(89)90032-9","volume":"38","author":"M. Yannakakis","year":"1989","unstructured":"M. Yannakakis. Embedding planar graphs in four pages. J. of Comp. and Sys. Sci., 38:36\u201367, 1989.","journal-title":"J. of Comp. and Sys. Sci."}],"container-title":["Lecture Notes in Computer Science","STACS 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36494-3_44","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T15:01:06Z","timestamp":1558969266000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36494-3_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540006237","9783540364948"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/3-540-36494-3_44","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}