{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:10:53Z","timestamp":1725541853726},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642114083"},{"type":"electronic","value":"9783642114090"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-11409-0_2","type":"book-chapter","created":{"date-parts":[[2009,12,3]],"date-time":"2009-12-03T13:12:27Z","timestamp":1259845947000},"page":"17-32","source":"Crossref","is-referenced-by-count":5,"title":["Algorithms for Classes of Graphs with Bounded Expansion"],"prefix":"10.1007","author":[{"given":"Zden\u011bk","family":"Dvo\u0159\u00e1k","sequence":"first","affiliation":[]},{"given":"Daniel","family":"Kr\u00e1l\u2019","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0012-365X(90)90292-P","volume":"80","author":"S. Arnborg","year":"1990","unstructured":"Arnborg, S., Proskurowski, A., Corneil, D.G.: Forbidden minors characterization of partial 3-trees. Discrete Math.\u00a080, 1\u201319 (1990)","journal-title":"Discrete Math."},{"key":"2_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1007\/3-540-59071-4_56","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Deogun, J.S., Jansen, K., Kloks, T., Kratsch, D., M\u00fcller, H., Tuza, Z.: Ranking of graphs. In: Mayr, E.W., Schmidt, G., Tinhofer, G. (eds.) WG 1994. LNCS, vol.\u00a0903, pp. 292\u2013304. Springer, Heidelberg (1995)"},{"key":"2_CR3","first-page":"1305","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Gilbert, J.R., Hafsteinsson, H., Kloks, T.: Approximating treewidth, pathwidth, frontsize and shortest elimination tree. J. Algorithms\u00a025, 1305\u20131317 (1996)","journal-title":"J. Algorithms"},{"key":"2_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/3-540-48447-7_34","volume-title":"Algorithms and Data Structures","author":"G.S. Brodal","year":"1999","unstructured":"Brodal, G.S., Fagelberg, R.: Dynamic representations of sparse graphs. In: Dehne, F., Gupta, A., Sack, J.-R., Tamassia, R. (eds.) WADS 1999. LNCS, vol.\u00a01663, pp. 342\u2013351. Springer, Heidelberg (1999)"},{"key":"2_CR5","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graph I.\u00a0Recognizable sets of finite graphs. Inform.\u00a0and Comput.\u00a085, 12\u201375 (1990)","journal-title":"Inform.\u00a0and Comput."},{"key":"2_CR6","first-page":"270","volume-title":"Proc.\u00a0LICS 2007","author":"A. Dawar","year":"2007","unstructured":"Dawar, A., Grohe, M., Kreutzer, S.: Locally excluding a minor. In: Proc.\u00a0LICS 2007, pp. 270\u2013279. IEEE Computer Society Press, Los Alamitos (2007)"},{"key":"2_CR7","doi-asserted-by":"crossref","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.\u00a0Combin.\u00a0Theory Ser.\u00a0B\u00a091, 25\u201341 (2004)","journal-title":"J.\u00a0Combin.\u00a0Theory Ser.\u00a0B"},{"unstructured":"Dvo\u0159\u00e1k, Z.: Assymptotical structure of combinatorial objects, PhD thesis, Charles University (2007)","key":"2_CR8"},{"doi-asserted-by":"crossref","unstructured":"Dvo\u0159\u00e1k, Z., Kr\u00e1l\u2019, D., Thomas, R.: Deciding first order properties for nowhere dense graphs (manuscript) (2009)","key":"2_CR9","DOI":"10.1109\/FOCS.2010.20"},{"unstructured":"Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. In: Proc.\u00a0SODA 1995, pp. 632\u2013640. ACM&SIAM (1995)","key":"2_CR10"},{"key":"2_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1186810.1186811","volume":"3","author":"D. Eppstein","year":"1999","unstructured":"Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. J.\u00a0Graph Algorithms Appl.\u00a03, 1\u201327 (1999)","journal-title":"J.\u00a0Graph Algorithms Appl."},{"key":"2_CR12","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s004530010020","volume":"27","author":"D. Eppstein","year":"2000","unstructured":"Eppstein, D.: Diameter and treewidth in minor-closed graph families. Algorithmica\u00a027, 275\u2013291 (2000)","journal-title":"Algorithmica"},{"key":"2_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/3-540-48523-6_30","volume-title":"Automata, Languages and Programming","author":"M. Frick","year":"1999","unstructured":"Frick, M., Grohe, M.: Deciding first-order properties of locally tree-decomposable structures. In: Wiedermann, J., Van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol.\u00a01644, pp. 331\u2013340. Springer, Heidelberg (1999)"},{"key":"2_CR14","first-page":"1184","volume":"48","author":"M. Frick","year":"2001","unstructured":"Frick, M., Grohe, M.: Deciding first-order properties of locally tree-decomposable structures. J.\u00a0ACM\u00a048, 1184\u20131206 (2001)","journal-title":"J.\u00a0ACM"},{"key":"2_CR15","volume-title":"Proc.\u00a0Herbrand Symp.\u00a0Logic Colloq.","author":"H. Gaifman","year":"1982","unstructured":"Gaifman, H.: On local and non-local properties. In: Proc.\u00a0Herbrand Symp.\u00a0Logic Colloq. North-Holland, Amsterdam (1982)"},{"key":"2_CR16","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/j.ipl.2006.12.006","volume":"102","author":"L. Kowalik","year":"2007","unstructured":"Kowalik, L.: Adjacency queries in dynamic sparse graphs. Inf.\u00a0Process.\u00a0Lett.\u00a0102, 191\u2013195 (2007)","journal-title":"Inf.\u00a0Process.\u00a0Lett."},{"key":"2_CR17","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1145\/1159892.1159895","volume":"2","author":"L. Kowalik","year":"2006","unstructured":"Kowalik, L., Kurowski, M.: Oracles for bounded-length shortest paths in planar graphs. ACM Trans.\u00a0Algorithms\u00a02, 335\u2013363 (2006)","journal-title":"ACM Trans.\u00a0Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Kowalik, L., Kurowski, M.: Short path queries in planar graphs in constant time. In: Proc.\u00a0STOC 2003, pp. 143\u2013148 (2003)","key":"2_CR18","DOI":"10.1145\/780542.780565"},{"unstructured":"Ne\u0161et\u0159il, J., Ossona de Mend\u00e9z, P.: First order properties of nowhere dense structures (manuscript) (2008)","key":"2_CR19"},{"key":"2_CR20","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1016\/j.ejc.2006.07.013","volume":"29","author":"J. Ne\u0161et\u0159il","year":"2008","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mend\u00e9z, P.: Grad and classes with bounded expansion I.\u00a0Decompositions. European J.\u00a0Combin.\u00a029, 760\u2013776 (2008)","journal-title":"European J.\u00a0Combin."},{"key":"2_CR21","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1016\/j.ejc.2006.07.014","volume":"29","author":"J. Ne\u0161et\u0159il","year":"2008","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mend\u00e9z, P.: Grad and classes with bounded expansion II. Algorithmic aspects. European J.\u00a0Combin.\u00a029, 777\u2013791 (2008)","journal-title":"European J.\u00a0Combin."},{"key":"2_CR22","doi-asserted-by":"publisher","first-page":"1012","DOI":"10.1016\/j.ejc.2007.11.019","volume":"29","author":"J. Ne\u0161et\u0159il","year":"2008","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mend\u00e9z, P.: Grad and classes with bounded expansion III.\u00a0Restricted graph homomorphism dualities. European J.\u00a0Combin.\u00a029, 1012\u20131024 (2008)","journal-title":"European J.\u00a0Combin."},{"doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mend\u00e9z, P.: Linear time low tree-width partitions and algorithmic consequences. In: Proc.\u00a0STOC 2006, pp. 391\u2013400 (2006)","key":"2_CR23","DOI":"10.1145\/1132516.1132575"},{"unstructured":"Ne\u0161et\u0159il, J., Ossona de Mend\u00e9z, P.: On nowhere dense graphs (manuscript) (2008)","key":"2_CR24"},{"doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mend\u00e9z, P.: Structural properties of sparse graphs (manuscript) (2008)","key":"2_CR25","DOI":"10.1007\/978-3-540-85221-6_13"},{"key":"2_CR26","doi-asserted-by":"publisher","first-page":"1022","DOI":"10.1016\/j.ejc.2005.01.010","volume":"27","author":"J. Ne\u0161et\u0159il","year":"2006","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mend\u00e9z, P.: Tree depth, subgraph coloring and homomorphism bounds. European J.\u00a0Combin.\u00a027, 1022\u20131041 (2006)","journal-title":"European J.\u00a0Combin."},{"unstructured":"Ne\u0161et\u0159il, J., Ossona de Mend\u00e9z, P., Wood, D.: Characterizations and examples of graph classes with bounded expansion (manuscript) (2008)","key":"2_CR27"},{"key":"2_CR28","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1006\/inco.1993.1020","volume":"103","author":"D. Peleg","year":"1993","unstructured":"Peleg, D.: Distance-dependent distributed directories. Info.\u00a0Computa.\u00a0103, 270\u2013298 (1993)","journal-title":"Info.\u00a0Computa."},{"key":"2_CR29","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(86)90030-4","volume":"B 41","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors V: Excluding a planar graph. J.\u00a0Combin.\u00a0Theory Ser.\u00a0B 41, 92\u2013114 (1986)","journal-title":"J.\u00a0Combin.\u00a0Theory Ser."},{"key":"2_CR30","first-page":"325","volume":"B 92","author":"N. Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.D.: Graph Minors XX.\u00a0Wagner\u2019s conjecture. J. Combin. Theory Ser.\u00a0B 92, 325\u2013357 (2004)","journal-title":"J. Combin. Theory Ser."},{"key":"2_CR31","first-page":"505","volume":"6","author":"D. Seese","year":"1996","unstructured":"Seese, D.: Linear time computable problems and first-order descriptions. Math.\u00a0Structu.\u00a0Comput.\u00a0Sci.\u00a06, 505\u2013526 (1996)","journal-title":"Math.\u00a0Structu.\u00a0Comput.\u00a0Sci."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11409-0_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:40:20Z","timestamp":1606185620000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-11409-0_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642114083","9783642114090"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11409-0_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}