{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T21:21:30Z","timestamp":1725571290395},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642175138"},{"type":"electronic","value":"9783642175145"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-17514-5_8","type":"book-chapter","created":{"date-parts":[[2010,12,3]],"date-time":"2010-12-03T20:09:23Z","timestamp":1291406963000},"page":"85-96","source":"Crossref","is-referenced-by-count":10,"title":["Improved Bounds on the Planar Branchwidth with Respect to the Largest Grid Minor Size"],"prefix":"10.1007","author":[{"given":"Qian-Ping","family":"Gu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hisao","family":"Tamaki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"8_CR1","doi-asserted-by":"publisher","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. ACM\u00a041, 153\u2013180 (1994)","journal-title":"J. ACM"},{"key":"8_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science\u00a0209, 1\u201345 (1998)","journal-title":"Theoretical Computer Science"},{"key":"8_CR3","doi-asserted-by":"publisher","first-page":"939","DOI":"10.1016\/j.comgeo.2009.05.001","volume":"42","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Feremans, C., Grigoriev, A., Penninkx, E., Sitters, R., Wolle, T.: On the minimum corridor connection problem and other generalized geometric problems. Computational Geometry: Theory and Applications\u00a042, 939\u2013951 (2009)","journal-title":"Computational Geometry: Theory and Applications"},{"issue":"1","key":"8_CR4","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/s00453-007-9056-z","volume":"51","author":"H.L. Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Grigoriev, A., Koster, A.M.C.A.: Treewidth lower bounds with brambles. Algorithmica\u00a051(1), 81\u201398 (2008)","journal-title":"Algorithmica"},{"key":"8_CR5","unstructured":"Dorn, F., Fomin, F.V., Thilikos, D.M.: Catalan structures and dynamic programming in H-minor-free graphs. In: Proc. of the 2008 Symposium on Discrete Algorithms, SODA 2008, pp. 631\u2013640 (2008)"},{"key":"8_CR6","unstructured":"Demaine, E.D., Hajiaghayi, M.T.: Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality. In: Proc. of the 2005 Symposium on Discrete Algorithms, SODA 2005, pp. 682\u2013689 (2005)"},{"key":"8_CR7","unstructured":"Demaine, E.D., Hajiaghayi, M.T.: Bidimensionality, map graphs, and grid minors, arXiv:Computer Science, DM\/052070, v1 (2005)"},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Hajiaghayi, M.T., Kawarabayashi, K.: Algorithmic graph minor theory: decomposition, approximation, and coloring. In: Proc. of the 2005 IEEE Symposium on Foundation of Computer Science, FOCS 2005, pp. 637\u2013646 (2005)","DOI":"10.1109\/SFCS.2005.14"},{"key":"8_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/11561071_11","volume-title":"Algorithms \u2013 ESA 2005","author":"F. Dorn","year":"2005","unstructured":"Dorn, F., Penninkx, E., Bodlaender, H.L., Fomin, F.V.: Efficient exact algorithms on planar graphs: exploiting sphere cut branch decompositions. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 95\u2013106. Springer, Heidelberg (2005)"},{"key":"8_CR10","unstructured":"Grigoriev, A.: Tree-width and large grid minors in planar graphs (2008) (submitted for publication)"},{"key":"8_CR11","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/j.endm.2009.02.006","volume":"32","author":"A. Grigoriev","year":"2009","unstructured":"Grigoriev, A., Marchal, B., Usotskaya, N.: On planar graphs with large treewidth and small grid minors. Electronic Notes in Discrete Mathematics\u00a032, 35\u201342 (2009)","journal-title":"Electronic Notes in Discrete Mathematics"},{"issue":"3","key":"8_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1367064.1367070","volume":"4","author":"Q.P. Gu","year":"2008","unstructured":"Gu, Q.P., Tamaki, H.: Optimal branch decomposition of planar graphs in O(n 3) time. ACM Trans. Algorithms\u00a04(3), article No.30, 1\u201313 (2008)","journal-title":"ACM Trans. Algorithms"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Gu, Q.P., Tamaki, H.: Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in O(n 1\u2009+\u2009\u03b5 ) time. In: Proc. of the 2009 International Symposium on Algorithms and Computation (ISAAC 2009), pp. 984\u2013993 (2009)","DOI":"10.1007\/978-3-642-10631-6_99"},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"Gu, Q.P., Tamaki, H.: Improved bounds on the planar branchwidth with respect to the largest grid minor size, Technical Report, SFU-CMPT-TR 2009-17 (July 2009)","DOI":"10.1007\/978-3-642-17514-5_8"},{"key":"8_CR15","unstructured":"Gu, Q.P., Tamaki, H.: A radius-based linear-time-constructive upper bound on the branchwidth of planar hypergrpahs, Technical Report, SFU-CMPT-TR 2009-21 (November 2009)"},{"key":"8_CR16","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":"8_CR17","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N. Robertson","year":"1991","unstructured":"Robertson, N., Seymour, P.D.: Graph minors X. Obstructions to tree decomposition. J. of Combinatorial Theory, Series B\u00a052, 153\u2013190 (1991)","journal-title":"J. of Combinatorial Theory, Series B"},{"key":"8_CR18","doi-asserted-by":"publisher","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. of Combinatorial Theory, Series B\u00a062, 323\u2013348 (1994)","journal-title":"J. of Combinatorial Theory, Series B"},{"issue":"2","key":"8_CR19","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"P.D. Seymour","year":"1994","unstructured":"Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica\u00a014(2), 217\u2013241 (1994)","journal-title":"Combinatorica"},{"key":"8_CR20","unstructured":"Thomas, R.: Tree decompositions of graphs, http:\/\/www.math.gatech.edu\/~thomas\/SLIDE\/slide2.ps,p.32"},{"key":"8_CR21","doi-asserted-by":"crossref","unstructured":"Tamaki, H.: A linear time heuristic for the branch-decomposition of planar graphs. In: Proc. of 11th Annual European Symposium on Algorithms, pp. 765\u2013775 (2003)","DOI":"10.1007\/978-3-540-39658-1_68"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17514-5_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T19:49:13Z","timestamp":1559850553000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17514-5_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642175138","9783642175145"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17514-5_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}