{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T10:36:05Z","timestamp":1756463765354},"publisher-location":"Berlin, Heidelberg","reference-count":48,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540245285"},{"type":"electronic","value":"9783540318439"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/978-3-540-31843-9_57","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T20:54:14Z","timestamp":1278363254000},"page":"517-533","source":"Crossref","is-referenced-by-count":14,"title":["Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth"],"prefix":"10.1007","author":[{"given":"Erik D.","family":"Demaine","sequence":"first","affiliation":[]},{"given":"MohammadTaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"57_CR1","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","volume":"33","author":"J. Alber","year":"2002","unstructured":"Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica\u00a033(4), 461\u2013493 (2002)","journal-title":"Algorithmica"},{"key":"57_CR2","doi-asserted-by":"crossref","unstructured":"Alber, J., Fan, H., Fellows, M.R., Fernau, H., Niedermeier, R., Rosamond, F.A., Stege, U.: Refined search tree technique for DOMINATING SET on planar graphs. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol.\u00a02136, pp. 111\u2013122. Springer, Heidelberg (2001)","DOI":"10.1007\/3-540-44683-4_11"},{"issue":"4","key":"57_CR3","doi-asserted-by":"crossref","first-page":"808","DOI":"10.1016\/S0022-0000(03)00072-2","volume":"67","author":"J. Alber","year":"2003","unstructured":"Alber, J., Fernau, H., Niedermeier, R.: Graph separators: a parameterized view. J. Comput. System Sci.\u00a067(4), 808\u2013832 (2003)","journal-title":"J. Comput. System Sci."},{"issue":"1","key":"57_CR4","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1016\/j.jalgor.2004.03.005","volume":"52","author":"J. Alber","year":"2004","unstructured":"Alber, J., Fernau, H., Niedermeier, R.: Parameterized complexity: exponential speed-up for planar graph problems. J. Algorithms\u00a052(1), 26\u201356 (2004)","journal-title":"J. Algorithms"},{"key":"57_CR5","unstructured":"Arora, S., Grigni, M., Karger, D., Klein, P., Woloszyn, A.: A polynomialtime approximation scheme for weighted planar graph TSP. In: Proc. 9th ACMSIAM Symp. Discr. Alg., pp. 33\u201341 (1998)"},{"issue":"4","key":"57_CR6","doi-asserted-by":"crossref","first-page":"801","DOI":"10.1090\/S0894-0347-1990-1065053-0","volume":"3","author":"N. Alon","year":"1990","unstructured":"Alon, N., Seymour, P., Thomas, R.: A separator theorem for nonplanar graphs. J. Amer. Math. Soc.\u00a03(4), 801\u2013808 (1990)","journal-title":"J. Amer. Math. Soc."},{"issue":"1","key":"57_CR7","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. Assoc. Comput. Mach.\u00a041(1), 153\u2013180 (1994)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"2","key":"57_CR8","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1145\/506147.506148","volume":"49","author":"Z.-Z. Chen","year":"2002","unstructured":"Chen, Z.-Z., Grigni, M., Papadimitriou, C.H.: Map graphs. J. ACM\u00a049(2), 127\u2013138 (2002)","journal-title":"J. ACM"},{"key":"57_CR9","doi-asserted-by":"crossref","unstructured":"Chang, M.-S., Kloks, T., Lee, C.-M.: Maximum clique transversals. In: Brandst\u00e4dt, A., Le, V.B. (eds.) WG 2001. LNCS, vol.\u00a02204, pp. 32\u201343. Springer, Heidelberg (2001)","DOI":"10.1007\/3-540-45477-2_5"},{"key":"#cr-split#-57_CR10.1","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Fixedparameter algorithms for the (k, r)-center in planar graphs and map graphs (to appear);"},{"key":"#cr-split#-57_CR10.2","unstructured":"A preliminary version appears. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 829\u2013844. Springer, Heidelberg (2003)"},{"key":"#cr-split#-57_CR11.1","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Bidimensional parameters and local treewidth (to appear);"},{"key":"#cr-split#-57_CR11.2","unstructured":"A preliminary version appears. In: LATIN 2004. LNCS, vol.\u00a02976, pp. 109\u2013118. Springer, Heidelberg (2004)"},{"key":"57_CR12","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs. In: Proc. 15th ACM-SIAM Symp. Discr. Alg., pp. 823\u2013832 (2004)"},{"issue":"3","key":"57_CR13","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/s00453-004-1106-1","volume":"40","author":"E.D. Demaine","year":"2004","unstructured":"Demaine, E.D., Hajiaghayi, M.: Diameter and treewidth in minor-closed graph families, revisited. Algorithmica\u00a040(3), 211\u2013215 (2004)","journal-title":"Algorithmica"},{"key":"57_CR14","unstructured":"Demaine, E.D., Hajiaghayi, M.: Equivalence of local treewidth and linear local treewidth and its algorithmic applications. In: Proc. 15th ACM-SIAM Symp. Discr. Alg., pp. 833\u2013842 (2004)"},{"key":"57_CR15","unstructured":"Demaine, E.D., Hajiaghayi, M.: Quickly deciding minor-closed parameters in general graphs. Manuscript (2004)"},{"key":"57_CR16","unstructured":"Demaine, E.D., Hajiaghayi, M.: Bidimensionality: New connections between FPT algorithms and PTASs. In: Proc. 16th ACM-SIAM Symp. Discr. Alg. (2005) (to appear)"},{"key":"57_CR17","unstructured":"Demaine, E.D., Hajiaghayi, M.: Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality. In: Proc. 16th ACM-SIAM Symp. Discr. Alg. (2005) (to appear)"},{"issue":"2","key":"57_CR18","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/j.jcss.2003.12.001","volume":"69","author":"E.D. Demaine","year":"2004","unstructured":"Demaine, E.D., Hajiaghayi, M., Nishimura, N., Ragde, P., Thilikos, D.M.: Approximation algorithms for classes of graphs excluding single-crossing graphs as minors. J. Comput. System Sci.\u00a069(2), 166\u2013195 (2004)","journal-title":"J. Comput. System Sci."},{"key":"#cr-split#-57_CR19.1","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Hajiaghayi, M., Thilikos, D.M.: Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors. Algorithmica (to appear);","DOI":"10.1007\/s00453-004-1125-y"},{"key":"#cr-split#-57_CR19.2","unstructured":"A preliminary version appears. In: ISAAC 2002. LNCS, vol.\u00a02518, pp. 262\u2013273. Springer, Heidelberg (2002)"},{"key":"57_CR20","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Hajiaghayi, M., Thilikos, D.M.: The bidimensional theory of bounded-genus graphs. In: Proc. 29th Internat. Symp. Math. Found. Comput. Sci., pp. 191\u2013203 (2004)","DOI":"10.1007\/978-3-540-28629-5_12"},{"issue":"1","key":"57_CR21","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1006\/jctb.1998.1862","volume":"75","author":"R. Diestel","year":"1999","unstructured":"Diestel, R., Jensen, T.R., Gorbunov, K.Y., Thomassen, C.: Highly connected sets and the excluded grid theorem. J. Combin. Theory Ser. B\u00a075(1), 61\u201373 (1999)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"4","key":"57_CR22","doi-asserted-by":"crossref","first-page":"1231","DOI":"10.1137\/S0097539798340047","volume":"30","author":"G. Even","year":"2000","unstructured":"Even, G., Naor, J., Zosin, L.: An 8-approximation algorithm for the subset feedback vertex set problem. SIAM J. Comput.\u00a030(4), 1231\u20131252 (2000)","journal-title":"SIAM J. Comput."},{"key":"57_CR23","unstructured":"Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. In: Proc. 6th ACM-SIAM Symp. Discr. Alg., pp. 632\u2013640 (1995)"},{"issue":"3-4","key":"57_CR24","doi-asserted-by":"crossref","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(3-4), 275\u2013291 (2000)","journal-title":"Algorithmica"},{"issue":"6","key":"57_CR25","doi-asserted-by":"crossref","first-page":"1184","DOI":"10.1145\/504794.504798","volume":"48","author":"M. Frick","year":"2001","unstructured":"Frick, M., Grohe, M.: Deciding first-order properties of locally treedecomposable structures. Journal of the ACM\u00a048(6), 1184\u20131206 (2001)","journal-title":"Journal of the ACM"},{"key":"57_CR26","unstructured":"Feige, U., Hajiaghayi, M., Lee, J.R.: On improving approximate vertex separator and its algorithmic applications. Manuscript (2004)"},{"issue":"3","key":"57_CR27","doi-asserted-by":"crossref","first-page":"727","DOI":"10.1145\/44483.44491","volume":"35","author":"M.R. Fellows","year":"1988","unstructured":"Fellows, M.R., Langston, M.A.: Nonconstructive tools for proving polynomial-time decidability. Journal of the ACM\u00a035(3), 727\u2013739 (1988)","journal-title":"Journal of the ACM"},{"key":"57_CR28","doi-asserted-by":"crossref","unstructured":"Friedman, H., Robertson, N., Seymour, P.: The metamathematics of the graph minor theorem. In: Logic and combinatorics. Contemp. Math., vol.\u00a065, pp. 229\u2013261. Amer. Math. Soc., Providence (1987)","DOI":"10.1090\/conm\/065\/891251"},{"key":"57_CR29","unstructured":"Fomin, F.V., Thilikos, D.M.: Dominating sets in planar graphs: Branchwidth and exponential speed-up. In: Proc. 14th ACM-SIAM Sympos. Discrete Algorithms, pp. 168\u2013177 (2003)"},{"key":"57_CR30","unstructured":"Gutin, G., Kloks, T., Lee, C.M.: Kernels in planar digraphs. In: Optimization Online (2001)"},{"issue":"4","key":"57_CR31","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1007\/s00493-003-0037-9","volume":"23","author":"M. Grohe","year":"2003","unstructured":"Grohe, M.: Local tree-width, excluded minors, and approximation algorithms. Combinatorica\u00a023(4), 613\u2013632 (2003)","journal-title":"Combinatorica"},{"key":"57_CR32","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M., Nishimura, N.: Subgraph isomorphism, log-bounded fragmentation and graphs of (locally) bounded treewidth. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol.\u00a02420, pp. 305\u2013318. Springer, Heidelberg (2002)","DOI":"10.1007\/3-540-45687-2_25"},{"key":"57_CR33","doi-asserted-by":"crossref","unstructured":"Kloks, T., Lee, C.M., Liu, J.: New algorithms for k-face cover, k-feedback vertex set, and k-disjoint set on plane and planar graphs. In: Ku\u010dera, L. (ed.) WG 2002. LNCS, vol.\u00a02573, pp. 282\u2013295. Springer, Heidelberg (2002)","DOI":"10.1007\/3-540-36379-3_25"},{"key":"57_CR34","doi-asserted-by":"crossref","unstructured":"Kanj, I.A., Perkovi\u0107, L.: Improved parameterized algorithms for planar dominating set. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol.\u00a02420, pp. 399\u2013410. Springer, Heidelberg (2002)","DOI":"10.1007\/3-540-45687-2_33"},{"issue":"3","key":"57_CR35","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R.J. Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput.\u00a09(3), 615\u2013627 (1980)","journal-title":"SIAM J. Comput."},{"key":"57_CR36","doi-asserted-by":"crossref","unstructured":"Reed, B.A.: Tree width and tangles: a new connectivity measure and some applications. In: Surveys in combinatorics. London Math. Soc. Lecture Note Ser., vol.\u00a0241, pp. 87\u2013162. Cambridge Univ. Press, Cambridge (1997)","DOI":"10.1017\/CBO9780511662119.006"},{"key":"57_CR37","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner\u2019s conjecture. J. Combin. Theory Ser. B (to appear)","DOI":"10.1016\/j.jctb.2004.08.001"},{"issue":"3","key":"57_CR38","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms\u00a07(3), 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"issue":"1","key":"57_CR39","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0095-8956(86)90030-4","volume":"41","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. V. Excluding a planar graph. J. Combin. Theory Ser. B\u00a041(1), 92\u2013114 (1986)","journal-title":"J. Combin. Theory Ser. B"},{"key":"57_CR40","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.: Excluding a graph with one crossing. In: Graph structure theory, pp. 669\u2013675. Amer. Math. Soc. (1993)","DOI":"10.1090\/conm\/147\/01206"},{"issue":"2","key":"57_CR41","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1006\/jctb.1995.1034","volume":"64","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XII. Distance on a surface. J. Combin. Theory Ser. B\u00a064(2), 240\u2013272 (1995)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"57_CR42","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0095-8956(03)00042-X","volume":"89","author":"N. Robertson","year":"2003","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XVI. Excluding a non-planar graph. J. Combin. Theory Ser. B\u00a089(1), 43\u201376 (2003)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"57_CR43","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1006\/jctb.1994.1073","volume":"62","author":"N. Robertson","year":"1994","unstructured":"Robertson, N., Seymour, P.D., Thomas, R.: Quickly excluding a planar graph. J. Combin. Theory Ser. B\u00a062(2), 323\u2013348 (1994)","journal-title":"J. Combin. Theory Ser. B"},{"key":"57_CR44","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Map graphs in polynomial time. In: Proc. 39th IEEE Sympos. Found. Comput. Sci., pp. 396\u2013407 (1998)","DOI":"10.1109\/SFCS.1998.743490"},{"key":"57_CR45","first-page":"280","volume":"2","author":"K Wagner","year":"1937","unstructured":"Wagner, K.: \u00dcber eine Eigenschaft der eben Komplexe. Deutsche Math.\u00a02, 280\u2013285 (1937)","journal-title":"Deutsche Math."}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-31843-9_57.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T03:42:07Z","timestamp":1620013327000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-31843-9_57"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540245285","9783540318439"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-31843-9_57","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}