Abstract
For graph G, let bw(G) denote the branchwidth of G and gm(G) the largest integer g such that G contains a g×g grid as a minor. We show that bw(G) ≤ 3gm(G) + 1 for every planar graph G. This is an improvement over the bound bw(G) ≤ 4gm(G) due to Robertson, Seymour and Thomas. Our proof is constructive and implies quadratic time constant-factor approximation algorithms for planar graphs for both problems of finding a largest grid minor and of finding an optimal branch-decomposition: (3 + ε)-approximation for the former and (2 + ε)-approximation for the latter, where ε is an arbitrary positive constant. We also study the tightness of the above bound. A k×h cylinder, denoted by C k,h , is the Cartesian product of a cycle on k vertices and a path on h vertices. We show that bw(C 2h, h ) = 2gm(C 2h,h ) = 2h and therefore the coefficient in the above upper bound is within a factor of 3/2 from the best possible.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41, 153–180 (1994)
Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science 209, 1–45 (1998)
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 42, 939–951 (2009)
Bodlaender, H.L., Grigoriev, A., Koster, A.M.C.A.: Treewidth lower bounds with brambles. Algorithmica 51(1), 81–98 (2008)
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–640 (2008)
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–689 (2005)
Demaine, E.D., Hajiaghayi, M.T.: Bidimensionality, map graphs, and grid minors, arXiv:Computer Science, DM/052070, v1 (2005)
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–646 (2005)
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. 3669, pp. 95–106. Springer, Heidelberg (2005)
Grigoriev, A.: Tree-width and large grid minors in planar graphs (2008) (submitted for publication)
Grigoriev, A., Marchal, B., Usotskaya, N.: On planar graphs with large treewidth and small grid minors. Electronic Notes in Discrete Mathematics 32, 35–42 (2009)
Gu, Q.P., Tamaki, H.: Optimal branch decomposition of planar graphs in O(n 3) time. ACM Trans. Algorithms 4(3), article No.30, 1–13 (2008)
Gu, Q.P., Tamaki, H.: Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in O(n 1 + ε) time. In: Proc. of the 2009 International Symposium on Algorithms and Computation (ISAAC 2009), pp. 984–993 (2009)
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)
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)
Robertson, N., Seymour, P.D.: Graph minors III. Planar tree-width. J. of Combinatorial Theory, Series B 36, 49–64 (1984)
Robertson, N., Seymour, P.D.: Graph minors X. Obstructions to tree decomposition. J. of Combinatorial Theory, Series B 52, 153–190 (1991)
Robertson, N., Seymour, P.D., Thomas, R.: Quickly excluding a planar graph. J. of Combinatorial Theory, Series B 62, 323–348 (1994)
Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica 14(2), 217–241 (1994)
Thomas, R.: Tree decompositions of graphs, http://www.math.gatech.edu/~thomas/SLIDE/slide2.ps,p.32
Tamaki, H.: A linear time heuristic for the branch-decomposition of planar graphs. In: Proc. of 11th Annual European Symposium on Algorithms, pp. 765–775 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gu, QP., Tamaki, H. (2010). Improved Bounds on the Planar Branchwidth with Respect to the Largest Grid Minor Size. In: Cheong, O., Chwa, KY., Park, K. (eds) Algorithms and Computation. ISAAC 2010. Lecture Notes in Computer Science, vol 6507. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17514-5_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-17514-5_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17513-8
Online ISBN: 978-3-642-17514-5
eBook Packages: Computer ScienceComputer Science (R0)