{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:09:01Z","timestamp":1760202541867},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540755197"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-75520-3_52","type":"book-chapter","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T03:46:33Z","timestamp":1189741593000},"page":"582-593","source":"Crossref","is-referenced-by-count":14,"title":["Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs"],"prefix":"10.1007","author":[{"given":"Cyril","family":"Gavoille","sequence":"first","affiliation":[]},{"given":"Arnaud","family":"Labourel","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"52_CR1","doi-asserted-by":"crossref","first-page":"1295","DOI":"10.1137\/S0097539703437211","volume":"35","author":"S. Abiteboul","year":"2006","unstructured":"Abiteboul, S., Alstrup, S., Kaplan, H., Milo, T., Rauhe, T.: Compact labeling schemes for ancestor queries. SIAM J. on Computing\u00a035, 1295 (2006)","journal-title":"SIAM J. on Computing"},{"key":"52_CR2","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1137\/S0895480103433409","volume":"19","author":"S. Alstrup","year":"2005","unstructured":"Alstrup, S., Bille, P., Rauhe, T.: Labeling schemes for small distances in trees. SIAM J. on Discrete Mathematics\u00a019, 448\u2013462 (2005)","journal-title":"SIAM J. on Discrete Mathematics"},{"key":"52_CR3","first-page":"53","volume-title":"FOCS","author":"S. Alstrup","year":"2002","unstructured":"Alstrup, S., Rauhe, T.: Small induced-universal graphs and compact implicit graph representations. In: FOCS. 43\n                    rd\n                   Annual IEEE Symp. on Foundations of Computer Science, nov, pp. 53\u201362. IEEE Computer Society Press, Los Alamitos (2002)"},{"key":"52_CR4","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. on Algeb. and Disc. Meth.\u00a08, 277\u2013284 (1987)","journal-title":"SIAM J. on Algeb. and Disc. Meth."},{"key":"52_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1122","DOI":"10.1007\/11602613_111","volume-title":"Algorithms and Computation","author":"F. Bazzaro","year":"2005","unstructured":"Bazzaro, F., Gavoille, C.: Localized and compact data-structure for comparability graphs. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, pp. 1122\u20131131. Springer, Heidelberg (2005)"},{"issue":"6","key":"52_CR6","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. on Computing\u00a025(6), 1305\u20131317 (1996)","journal-title":"SIAM J. on Computing"},{"key":"52_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/11780823_12","volume-title":"Structural Information and Communication Complexity","author":"N. Bonichon","year":"2006","unstructured":"Bonichon, N., Gavoille, C., Labourel, A.: Short labels by traversal and jumping. In: Flocchini, P., G\u0105sieniec, L. (eds.) SIROCCO 2006. LNCS, vol.\u00a04056, pp. 143\u2013156. Springer, Heidelberg (2006)"},{"key":"52_CR8","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1109\/TIT.1966.1053860","volume":"IT-12","author":"M.A. Breuer","year":"1966","unstructured":"Breuer, M.A.: Coding the vertexes of a graph. IEEE Transactions on Information Theory\u00a0IT-12, 148\u2013153 (1966)","journal-title":"IEEE Transactions on Information Theory"},{"key":"52_CR9","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1002\/jgt.3190140408","volume":"14","author":"F.R.K. Chung","year":"1990","unstructured":"Chung, F.R.K.: Universal graphs and induced-universal graphs. J. of Graph Theory\u00a014, 443\u2013454 (1990)","journal-title":"J. of Graph Theory"},{"issue":"1","key":"52_CR10","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.jctb.2003.09.001","volume":"91","author":"M. DeVos","year":"2004","unstructured":"DeVos, M., Ding, G., Oporowski, B., Sanders, D.P., Reed, B., Seymour, P.D., Vertigan, D.: Excluding any graph as a minor allows a low tree-width 2-coloring. J. of Combinatorial Theory, Series B\u00a091(1), 25\u201341 (2004)","journal-title":"J. of Combinatorial Theory, Series B"},{"key":"52_CR11","first-page":"69","volume":"66","author":"E.S. Elmallah","year":"1988","unstructured":"Elmallah, E.S., Colbourn, C.J.: Partitioning the edges of a planar graph into two partial k-trees. Congressus Numerantium\u00a066, 69\u201380 (1988)","journal-title":"Congressus Numerantium"},{"key":"52_CR12","first-page":"317","volume-title":"Colloq. Math. Soc. Janos Bolyai\u00a04: Combinatorial theory and its applications","author":"P. Erd\u00f6s","year":"1970","unstructured":"Erd\u00f6s, P., Gerencs\u00e9r, L., M\u00e1t\u00e9, A.: Problems of graph theory concerning optimal design. In: Colloq. Math. Soc. Janos Bolyai\u00a04: Combinatorial theory and its applications, vol.\u00a01, pp. 317\u2013325. North-Holland, Amsterdam (1970)"},{"key":"52_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1007\/3-540-48224-5_62","volume-title":"Automata, Languages and Programming","author":"P. Fraigniaud","year":"2001","unstructured":"Fraigniaud, P., Gavoille, C.: Routing in trees. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 757\u2013772. Springer, Heidelberg (2001)"},{"key":"52_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1007\/978-3-540-39658-1_25","volume-title":"Algorithms - ESA 2003","author":"C. Gavoille","year":"2003","unstructured":"Gavoille, C., Paul, C.: Optimal distance labeling schemes for interval and circular-arc graphs. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 254\u2013265. Springer, Heidelberg (2003)"},{"key":"52_CR15","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1137\/0605032","volume":"5","author":"J.R. Gilbert","year":"1984","unstructured":"Gilbert, J.R., Rose, D.J., Edenbrandt, A.: A separator theorem for chordal graphs. SIAM J. on Algebraic and Discrete Methods\u00a05, 306\u2013313 (1984)","journal-title":"SIAM J. on Algebraic and Discrete Methods"},{"key":"52_CR16","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1145\/1060590.1060666","volume-title":"STOC","author":"D. Gon\u00e7alves","year":"2005","unstructured":"Gon\u00e7alves, D.: Edge partition of planar graphs into two outerplanar graphs. In: STOC. 37\n                    th\n                   Annual ACM Symp. on Theory of Computing, pp. 504\u2013512. ACM Press, New York (2005)"},{"key":"52_CR17","unstructured":"\u00c9tude de diff\u00e9rents probl\u00e8mes de partition de graphes, PhD thesis, Universit\u00e9 Bordeaux 1, Talence, France (December 2006)"},{"key":"52_CR18","first-page":"334","volume-title":"STOC","author":"S. Kannan","year":"1988","unstructured":"Kannan, S., Naor, M., Rudich, S.: Implicit representation of graphs. In: STOC. 20\n                    th\n                   Annual ACM Symp. on Theory of Computing, pp. 334\u2013343. ACM Press, New York (1988)"},{"key":"52_CR19","series-title":"Lecture Notes in Computer Science","volume-title":"ICALP 2007","author":"A. Korman","year":"2007","unstructured":"Korman, A., Peleg, D.: Compact separator decompositions and routing in dynamics trees. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596. Springer, Heidelberg (2007)"},{"issue":"5","key":"52_CR20","doi-asserted-by":"publisher","first-page":"754","DOI":"10.1016\/j.jctb.2006.01.006","volume":"96","author":"S. Norine","year":"2006","unstructured":"Norine, S., Robertson, N., Thomas, R., Wollan, P.: Proper minor-closed families are small. J. of Combinatorial Theory, Series B\u00a096(5), 754\u2013757 (2006)","journal-title":"J. of Combinatorial Theory, Series B"},{"issue":"2","key":"52_CR21","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. on Computing\u00a031(2), 353\u2013363 (2001)","journal-title":"SIAM J. on Computing"},{"key":"52_CR22","first-page":"221","volume-title":"STOC","author":"B. Reed","year":"1992","unstructured":"Reed, B.: Finding approximate separators and computing treewidth quickly. In: STOC. 24\n                    th\n                   Annual ACM Symp. on Theory of Comp., pp. 221\u2013228. ACM Press, New York (1992)"},{"key":"52_CR23","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N. Robertson","year":"1984","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. III. planar tree-width. J. of Combinatorial Theory, Series B\u00a036, 49\u201364 (1984)","journal-title":"J. of Combinatorial Theory, Series B"},{"key":"52_CR24","first-page":"138","volume-title":"SODA","author":"W. Schnyder","year":"1990","unstructured":"Schnyder, W.: Embedding planar graphs on the grid. In: SODA. 1\n                    st\n                   Symp. on Discrete Algorithms, pp. 138\u2013148. ACM Press, New York (1990)"},{"key":"52_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/378580.378581","volume-title":"SPAA","author":"M. Thorup","year":"2001","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: SPAA. 13\n                    th\n                   Annual ACM Symp. on Parallel Algorithms and Architectures, pp. 1\u201310. ACM Press, New York (2001)"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-75520-3_52.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:22:58Z","timestamp":1619518978000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-75520-3_52"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540755197"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-75520-3_52","relation":{},"subject":[]}}