{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T08:07:32Z","timestamp":1742976452786,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":40,"publisher":"Birkh\u00e4user Boston","isbn-type":[{"type":"print","value":"9780817649036"},{"type":"electronic","value":"9780817649043"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-0-8176-4904-3_2","type":"book-chapter","created":{"date-parts":[[2011,8,24]],"date-time":"2011-08-24T17:01:55Z","timestamp":1314205315000},"page":"17-46","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Information-Theoretic Upper Bound on Planar Graphs Using Well-Orderly Maps"],"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":[[2011,6,11]]},"reference":[{"issue":"2","key":"2_CR1","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/BF02522824","volume":"17","author":"L Alonso","year":"1997","unstructured":"Alonso, L., R\u00e9my, J.L., Schott, R.: A linear-time algorithm for the generation of trees. Algorithmica 17(2), 162\u2013182 (1997)","journal-title":"Algorithmica"},{"key":"2_CR2","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1007\/3-540-45022-X_33","volume-title":"Automata, Languages and Programming","author":"Cyril Banderier","year":"2000","unstructured":"Banderier, C., Flajolet, P., Schaeffer, G., Soria, M.: Planar maps and airy phenomena. In: 27th International Colloquium on Automata, Languages and Programming (ICALP), vol. 1853 of Lecture Notes in Computer Science, pp. 388\u2013402. Springer, New York (2000)"},{"issue":"2","key":"2_CR3","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/S0304-3975(98)00322-3","volume":"218","author":"E Barcucci","year":"1999","unstructured":"Barcucci, E., del Lungo, A., Pergola, E.: Random generation of trees and other combinatorial objects. Theor. Comput. Sci. 218(2), 219\u2013232 (1999)","journal-title":"Theor. Comput. Sci."},{"unstructured":"Bodirsky, M., Kang, M.: Generating random outerplanar graphs. In: 1st Workshop on Algorithms for Listing, Counting, and Enumeration (ALICE) (2003)","key":"2_CR4"},{"unstructured":"Bonichon, N.: A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths. In: Formal Power Series & Algebraic Combinatorics (FPSAC) (2002)","key":"2_CR5"},{"key":"2_CR6","first-page":"499","volume-title":"Lecture Notes in Computer Science","author":"Nicolas Bonichon","year":"2003","unstructured":"Bonichon, N., Gavoille, C., Hanusse, N.: An information-theoretic upper bound of planar graphs using triangulation. In: 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS), vol. 2607 of Lecture Notes in Computer Science, pp. 499\u2013510. Springer, New York (2003)"},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00373-006-0647-2","volume":"22","author":"N Bonichon","year":"2006","unstructured":"Bonichon, N., Gavoille, C., Hanusse, N., Poulalhon, D., Schaeffer, G.: Planar graphs, via well-orderly maps and trees. Graph. Combinator. 22, 1\u201318 (2006)","journal-title":"Graph. Combinator."},{"unstructured":"Chiang, Y.T., Lin, C.C., Lu, H.I.: Orderly spanning trees with applications to graph encoding and graph drawing. In: 12th Symposium on Discrete Algorithms (SODA), pp. 506\u2013515. ACM-SIAM (2001)","key":"2_CR8"},{"issue":"1","key":"2_CR9","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/0022-0000(85)90004-2","volume":"30","author":"N Chiba","year":"1985","unstructured":"Chiba, N., Nishizeki, T., Abe, S., Ozawa, T.: A linear algorithm for embedding planar graphs using pq-trees. J. Comput. Syst. Sci. 30(1), 54\u201376 (1985)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"2_CR10","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/0022-0000(85)90004-2","volume":"30","author":"N Chiba","year":"1985","unstructured":"Chiba, N., Nishizeki, T., Abe, S., Ozawa, T.: A linear algorithm for embedding planar graphs using pq-trees. J. Comput. Syst. Sci. 30(1), 54\u201376 (1985)","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR11","first-page":"118","volume-title":"25th International Colloquium on Automata, Languages and Programming (ICALP), vol. 1443 of Lecture Notes in Computer Science","author":"RCN 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: Guldstrand\u00a0Larsen, K., Skyum, S., Winskel,\u00a0G. (eds.) 25th International Colloquium on Automata, Languages and Programming (ICALP), vol. 1443 of Lecture Notes in Computer Science, pp. 118\u2013129. Springer, New York (1998)"},{"key":"2_CR12","first-page":"61","volume":"113","author":"A Denise","year":"1996","unstructured":"Denise, A., Vasconcellos, M., Welsh, D.J.A.: The random planar graph. Congressus Numerantium 113, 61\u201379 (1996)","journal-title":"The random planar graph. Congressus Numerantium"},{"doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 2nd edn., vol. 173 of Graduate Texts in Mathematics. Springer, New York (2000)","key":"2_CR13","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"2_CR14","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1145\/189443.189446","volume":"4","author":"P Epstein","year":"1994","unstructured":"Epstein, P., Sack, J.R.: Generating triangulations at random. ACM Trans. Model. Comput. Simul. 4, 267\u2013278 (1994)","journal-title":"ACM Trans. Model. Comput. Simul."},{"issue":"4","key":"2_CR15","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1137\/0218058","volume":"18","author":"GN Frederickson","year":"1989","unstructured":"Frederickson, G.N., Janardan, R.: Efficient message routing in planar networks. SIAM J. Comput. 18(4), 843\u2013857 (1989)","journal-title":"SIAM J. Comput."},{"key":"2_CR16","first-page":"351","volume-title":"26th International Colloquium on Automata, Languages and Programming (ICALP), vol. 1644 of Lecture Notes in Computer Science","author":"C Gavoille","year":"1999","unstructured":"Gavoille, C., Hanusse, N.: Compact routing tables for graphs of bounded genus. In: Wiedermann, J., van Emde\u00a0Boas, P., Nielsen, M. (eds.) 26th International Colloquium on Automata, Languages and Programming (ICALP), vol. 1644 of Lecture Notes in Computer Science, pp. 351\u2013360. Springer, New York (1999)"},{"key":"2_CR17","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1017\/S0963548303005947","volume":"13","author":"S Gerke","year":"2004","unstructured":"Gerke, S., McDiarmid, C.J.H.: On the number of edges in random planar graphs. Combinator. Probab. Comput. 13, 165\u2013183 (2004)","journal-title":"Combinator. Probab. Comput."},{"key":"2_CR18","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1090\/S0894-0347-08-00624-3","volume":"22","author":"O Gim\u00e9nez","year":"2009","unstructured":"Gim\u00e9nez, O., Noy, M.: Asymptotic enumeration and limit laws of planar graphs. J. Am. Math. Soc. 22, 309\u2013329 (2009)","journal-title":"J. Am. Math. Soc."},{"issue":"3","key":"2_CR19","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. 30(3), 838\u2013846 (2000)","journal-title":"SIAM J. Comput."},{"key":"2_CR20","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. 58, 239\u2013252 (1995)","journal-title":"Discrete Appl. Math."},{"doi-asserted-by":"crossref","unstructured":"Khodakovsky, A., Alliez, P., Desbrun, M., Schr\u00f6der, P.: Near-optimal connectivity encoding of 2-manifold polygon meshes. Graph. Model. (2002). To appear in a special issue","key":"2_CR21","DOI":"10.1006\/gmod.2002.0575"},{"unstructured":"King, D., Rossignac, J.: Guaranteed 3.67V bit encoding of planar triangle graphs. In: 11th Canadian Conference on Computational Geometry (CCCG), pp. 146\u2013149 (1999)","key":"2_CR22"},{"issue":"2","key":"2_CR23","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"RJ Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"key":"2_CR24","first-page":"269","volume":"60","author":"VA Liskovets","year":"1987","unstructured":"Liskovets, V.A., Walsh, T.R.: Ten steps to counting planar graphs. Congressus Numerantium 60, 269\u2013277 (1987)","journal-title":"Congressus Numerantium"},{"key":"2_CR25","first-page":"97","volume":"34","author":"Y Liu","year":"1988","unstructured":"Liu, Y.: Enumeration of simple planar maps. Utilitas Math. 34, 97\u2013104 (1988)","journal-title":"Utilitas Math."},{"key":"2_CR26","first-page":"57","volume-title":"Lecture Notes in Computer Science","author":"Hsueh-I Lu","year":"2002","unstructured":"Lu, H.I.: Improved compact routing tables for planar networks via orderly spanning trees. In: 8th Annual International Computing & Combinatorics Conference (COCOON), vol. 2387 of Lecture Notes in Computer Science, pp. 57\u201366. Springer, New York (2002)"},{"unstructured":"Lu, H.I.: Linear-time compression of bounded-genus graphs into information-theoretically optimal number of bits. In: 13th Symposium on Discrete Algorithms (SODA), pp. 223\u2013224. ACM-SIAM (2002)","key":"2_CR27"},{"key":"2_CR28","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/j.jctb.2004.09.007","volume":"93","author":"CJH McDiarmid","year":"2005","unstructured":"McDiarmid, C.J.H., Steger, A., Welsh, D.J.A.: Random planar graphs. J. Combin. Theor. B 93, 187\u2013205 (2005)","journal-title":"J. Combin. Theor. B"},{"doi-asserted-by":"crossref","unstructured":"Munro, J.I., Raman, V.: Succinct representation of balanced parentheses, static trees and planar graphs. In: 38th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 118\u2013126. IEEE Computer Society Press (1997)","key":"2_CR29","DOI":"10.1109\/SFCS.1997.646100"},{"unstructured":"Nishizeki, T., Chiba, N.: Planar Graphs: Theory and Algorithms. North-Holland Mathematics Studies\u00a0140, Amsterdam (1988)","key":"2_CR30"},{"key":"2_CR31","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0095-8956(02)00040-0","volume":"88","author":"D Osthus","year":"2003","unstructured":"Osthus, D., Pr\u00f6mel, H.J., Taraz, A.: On random planar graphs, the number of planar graphs and their triangulations. J. Combin. Theor. B 88, 119\u2013134 (2003)","journal-title":"J. Combin. Theor. B"},{"issue":"2","key":"2_CR32","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1137\/S0097539700369909","volume":"31","author":"R Pagh","year":"2001","unstructured":"Pagh, R.: Low redundancy in static dictionaries with constant query time. SIAM J. Comput. 31(2), 353\u2013363 (2001)","journal-title":"SIAM J. Comput."},{"key":"2_CR33","doi-asserted-by":"publisher","first-page":"1080","DOI":"10.1007\/3-540-45061-0_83","volume-title":"Automata, Languages and Programming","author":"Dominique Poulalhon","year":"2003","unstructured":"Poulalhon, D., Schaeffer, G.: Optimal coding and sampling of triangulations. In: 30th International Colloquium on Automata, Languages and Programming (ICALP), vol. 2719 of Lecture Notes in Computer Science, pp. 1080\u20131094. Springer, New York (2003)"},{"issue":"1","key":"2_CR34","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. Visual. Comput. Graph. 5(1), 47\u201361 (1999)","journal-title":"IEEE Trans. Visual. Comput. Graph."},{"doi-asserted-by":"crossref","unstructured":"Schaeffer, G.: Random sampling of large planar maps and convex polyhedra. In: 31st Annual ACM Symposium on Theory of Computing (STOC), pp. 760\u2013769 (1999)","key":"2_CR35","DOI":"10.1145\/301250.301448"},{"unstructured":"Schnyder, W.: Embedding planar graphs on the grid. In: 1st Symposium on Discrete Algorithms (SODA), pp. 138\u2013148. ACM-SIAM (1990)","key":"2_CR36"},{"doi-asserted-by":"crossref","unstructured":"Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. In: 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 242\u2013251. IEEE Computer Society Press (2001)","key":"2_CR37","DOI":"10.1109\/SFCS.2001.959898"},{"key":"2_CR38","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0166-218X(84)90126-4","volume":"8","author":"G Tur\u00e1n","year":"1984","unstructured":"Tur\u00e1n, G.: Succinct representations of graphs. Discrete Appl. Math. 8, 289\u2013294 (1984)","journal-title":"Discrete Appl. Math."},{"key":"2_CR39","doi-asserted-by":"publisher","first-page":"21","DOI":"10.4153\/CJM-1962-002-9","volume":"14","author":"WT Tutte","year":"1962","unstructured":"Tutte, W.T.: A census of planar triangulations. Cana. J. Math. 14, 21\u201338 (1962)","journal-title":"Cana. J. Math."},{"key":"2_CR40","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/0022-0000(89)90032-9","volume":"38","author":"M Yannakakis","year":"1989","unstructured":"Yannakakis, M.: Embedding planar graphs in four pages. J. Comput. Syst. Sci. 38, 36\u201367 (1989)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Towards an Information Theory of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-8176-4904-3_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,9]],"date-time":"2025-03-09T06:35:43Z","timestamp":1741502143000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-0-8176-4904-3_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9780817649036","9780817649043"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-0-8176-4904-3_2","relation":{},"subject":[],"published":{"date-parts":[[2011]]},"assertion":[{"value":"11 June 2011","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}