{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T01:52:09Z","timestamp":1743040329566,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540662242"},{"type":"electronic","value":"9783540485230"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48523-6_32","type":"book-chapter","created":{"date-parts":[[2007,12,10]],"date-time":"2007-12-10T12:06:31Z","timestamp":1197288391000},"page":"351-360","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Compact Routing Tables for Graphs of Bounded Genus (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"Cyril","family":"Gavoille","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicolas","family":"Hanusse","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,1,18]]},"reference":[{"key":"32_CR1","first-page":"134","volume":"139","author":"T. Bilski","year":"1992","unstructured":"T. Bilski, Embedding graphs in books: A survey, IEE Proceedings-E, 139 (1992), pp. 134\u2013138.","journal-title":"IEE Proceedings-E"},{"key":"32_CR2","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1016\/0095-8956(79)90021-2","volume":"27","author":"F. Bernhart","year":"1979","unstructured":"F. Bernhart and P.C. Kainen, The book thickness of a graph, Journal of Combinatorial Theory, 27 (1979), pp. 320\u2013331.","journal-title":"Journal of Combinatorial Theory"},{"key":"32_CR3","series-title":"Lect Notes Comput Sci","first-page":"1","volume-title":"25th International Colloquium on Automata, Languages and Programming (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 International Colloquium on Automata, Languages and Programming (ICALP), K. Guldstrand Larsen, S. Skyum, and G. Winskel, eds., vol. 1443 of Lecture Notes in Computer Science, Springer, July 1998, pp. 1\u201312."},{"key":"32_CR4","first-page":"61","volume":"113","author":"A. Denise","year":"1996","unstructured":"A. Denise, M. Vasconcellos, and D. Welsh, The random planar graph, Congressus Numerantium, 113 (1996), pp. 61\u201379.","journal-title":"Congressus Numerantium"},{"key":"32_CR5","doi-asserted-by":"crossref","unstructured":"T. Eilam, C. Gavoille, and D. Peleg, Compact routing schemes with low stretch factor, in 17th Annual ACM Symposium on Principles of Distributed Computing (PODC), ACM PRESS, ed., August 1998, pp. 11\u201320.","DOI":"10.1145\/277697.277702"},{"key":"32_CR6","doi-asserted-by":"crossref","unstructured":"C. Gavoille and N. Hanusse, Compact routing tables for graphs of bounded genus, Research Report RR-1213-99, LaBRI, University of Bordeaux, 351 cours de la Lib\u00e9ration, 33405 Talence Cedex, France, February 1999. To appear in ICALP\u2019 99.","DOI":"10.1007\/3-540-48523-6_32"},{"key":"32_CR7","doi-asserted-by":"crossref","unstructured":"C. Gavoille and S. P\u00c9renn\u00c8s, Memory requirement for routing in distributed networks, in 15th Annual ACM Symposium on Principles of Distributed Computing (PODC), ACM PRESS, ed., May 1996, pp. 125\u2013133.","DOI":"10.1145\/248052.248075"},{"key":"32_CR8","doi-asserted-by":"crossref","unstructured":"L. Heath and S. Istrail, The pagenumber of genus g graphs is O(g), in 19th Annual ACM Symposium on Theory of Computing (STOC), 1987, pp. 388\u2013397.","DOI":"10.1145\/28395.28437"},{"key":"32_CR9","doi-asserted-by":"crossref","unstructured":"G. Jacobson, Space-efficient static trees and graphs, in 30th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society Press, October 1989, pp. 549\u2013554.","DOI":"10.1109\/SFCS.1989.63533"},{"key":"32_CR10","doi-asserted-by":"crossref","unstructured":"P. Klein, S. Rao, M. Rauch, and S. Subramanian, Faster shortest-path algorithms for planar graphs, in 26th Annual ACM Symposium on Theory of Computing (STOC), 1994, pp. 27\u201337.","DOI":"10.1145\/195058.195092"},{"key":"32_CR11","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":"32_CR12","doi-asserted-by":"crossref","unstructured":"S.M. Malitz, Genus g graphs have pagenumber O(pg), in 29th Symposium on Foundations of Computer Science (FOCS), IEEE, ed., October 1988, pp. 458\u2013468.","DOI":"10.1109\/SFCS.1988.21962"},{"key":"32_CR13","doi-asserted-by":"crossref","unstructured":"J.I. Munro and V. Raman, Succint representation of balanced parentheses, static trees and planar graphs, in 38rd Symposium on Foundations of Computer Science (FOCS), IEEE, ed., October 1997, pp. 118\u2013126.","DOI":"10.1109\/SFCS.1997.646100"},{"key":"32_CR14","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1145\/65950.65953","volume":"36","author":"D. Peleg","year":"1989","unstructured":"D. Peleg and E. Upfal, A trade-off between space and efficiency for routing tables, Journal of the ACM, 36 (1989), pp. 510\u2013530.","journal-title":"Journal of the ACM"},{"key":"32_CR15","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0166-218X(84)90126-4","volume":"8","author":"G. Tur\u00c1n","year":"1984","unstructured":"G. Tur\u00c1n, Succint representations of graphs, Discrete Applied Mathematics, 8 (1984), pp. 289\u2013294.","journal-title":"Discrete Applied Mathematics"},{"key":"32_CR16","doi-asserted-by":"publisher","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, Canadian Journal of Mathematics, 14 (1962), pp. 21\u201338.","journal-title":"Canadian Journal of Mathematics"},{"key":"32_CR17","doi-asserted-by":"crossref","unstructured":"M. Yannakakis, Four pages are necessary and sufficient for planar graphs, in 18th Annual ACM Symposium on Theory of Computing (STOC), 1986, pp. 104\u2013108.","DOI":"10.1145\/12130.12141"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48523-6_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T13:49:38Z","timestamp":1737640178000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/3-540-48523-6_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662242","9783540485230"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-48523-6_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1999]]},"assertion":[{"value":"18 January 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}