Planar Branch Decompositions I: The Ratcatcher

References

• Alber J., Niedermeier R. Improved tree decomposition based algorithms for domination-like problems. Fifth Latin American Theoret. Informatics (LATIN 2002) (2002) (Springer-Verlag, Berlin, Germany) 613–627Crossref, Google Scholar
• Alvarez C., Cases R., Diaz J., Petit J., Serna M. Routing tree problems on random graphs. (2000) . Technical report LSI-01-10-R, Software Department, Universitat Politecnica de Catalunya, Barcelona, SpainGoogle Scholar
• Archdeacon D. A Kuratowski theorem for the projective plane. (1980) . Ph.D. thesis, Mathematics Department, Ohio State University, Columbus, OHGoogle Scholar
• Archdeacon D., Huneke P. A Kuratowski theorem for non-orientable surfaces. J. Combin. Theory, Ser. B (1989) 46:173–231Crossref, Google Scholar
• Arnborg S., Lagergren J., Seese D. Easy problems for tree-decomposable graphs. J. Algorithms (1991) 12:308–340Crossref, Google Scholar
• Bienstock D. Graph searching, path-width, tree-width and related problems. Reliability of Computer and Communication Networks. Series Discrete Math. Theoret. Comput. Sci. (DIMACS) (1991) 5(American Mathematical Society, Providence, RI) 33–49Crossref, Google Scholar
• Bodlaender H. A tourist guide through treewidth. Acta Cybernetica (1993) 11:1–21Google Scholar
• Bodlaender H. A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. (1996) 25:1305–1317Crossref, Google Scholar
• Bodlaender H. Treewidth: Algorithmic techniques and results. 22nd Internat. Sympos. Math. Foundations Comput. Sci. (MFCS 1997) (1997) (Springer-Verlag, Berlin, Germany) 29–36LNCS, No. 1295Crossref, Google Scholar
• Bodlaender H. A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. (1998) 209:1–45Crossref, Google Scholar
• Bodlaender H., Kloks T. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms (1996) 21:358–402Crossref, Google Scholar
• Bodlaender H., Thilikos D. Constructive linear time algorithms for branchwidth. 24th Internat. Colloquium Automata, Languages, Programming (1997) (Springer-Verlag, Berlin, Germany) 627–637LNCS, No. 1256Crossref, Google Scholar
• Bodlaender H., Thilikos D. Graphs with branchwidth at most three. J. Algorithms (1999) 32:167–194Crossref, Google Scholar
• Borie R., Parker R., Tovey C. Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica (1992) 7:555–581Crossref, Google Scholar
• Bouchitte V., Mazolt F., Todinca I. Chordal embeddings of planar graphs. (2001) . Technical report RR-2001-03, Laboratoire d'Informatique Fondametale d'Orléans, Orleans, FranceGoogle Scholar
• Boyer J., Myrvold M. Stop minding your P's and Q's: A simplified O(n) planar embedding algorithm. Tenth Annual ACM-SIAM Sympos. Dicrete Algorithms (1999) (ACM, New York) 140–146Google Scholar
• Christian W. Linear-time algorithms for graphs with bounded branchwidth. (2003) . Ph.D. thesis, Computational and Applied Mathematics Department, Rice University, Houston, TXGoogle Scholar
• Cook W., Seymour P. Tour merging via branch-decomposition. INFORMS J. Comput. (2003) 15:233–248Link, Google Scholar
• Courcelle B. The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Inform. Comput. (1990) 85:12–75Crossref, Google Scholar
• Edelsbrunner H.Algorithms in Combinatorial Geometry (1987) (Springer-Verlag, Berlin, Germany) Crossref, Google Scholar
• Geelen J., Gerards A., Whittle G. Branch width and well-quasi-ordering in matroids and graphs. J. Comb. Theory, Ser. B (2002) 84:270–290Crossref, Google Scholar
• Glover H., Huneke P., Wang C. 103 graphs that are irreducible for the projective plane. J. Comb. Theory, Ser. B (1979) 27:332–370Crossref, Google Scholar
• Hicks I. V.Branch Decompositions and their Applications (2000) . Ph.D. thesis, Computational and Applied Mathematics Department, Rice University, Houston, TXGoogle Scholar
• Hicks I. V. Branchwidth heuristics. Congressus Numerantium (2002) 159:31–50Google Scholar
• Hicks I. V. Branch decompositions and minor containment. Networks (2004a) 43:1–9Crossref, Google Scholar
• Hicks I. V. New facets for the planar subgraph polytope. (2004b) . Working paper, Industrial Engineering Department, Texas A&M University, College Station, TXGoogle Scholar
• Hicks I. V. Planar branch decompositions II: The cycle method. INFORMS J. Comput. (2005) 17:418–421Google Scholar
• Kloks T., Kratochvil J., Müller H. New branchwidth territories. Sixteenth Annual Sympos. Theoret. Aspects Comput. Sci. Trier, Germany, March 1999 (1999) (Springer-Verlag, Berlin) 173–183Crossref, Google Scholar
• Koster A., Bodlaender H., van Hoesel S. Treewidth: Computational experiments. (2001) . Technical report 01-38, Konrad-Zuge, Zentrum für Informationstechnik Berlin, Berlin, GermanyGoogle Scholar
• Koster A., van Hoesel S., Kolen A. Solving partial constraint satisfaction problems with true decomposition. Networks (2002) 40:170–180Crossref, Google Scholar
• Kuratowski K. Sur le probleme des courbes gauches en topologie. Fundamenta Math. (1930) 15:271–283Crossref, Google Scholar
• Ramachandramurthi S. The structure and number of obstructions to treewidth. SIAM J. Discrete Math. (1997) 10:146–157Crossref, Google Scholar
• Reed B. Finding approximate separators and computing tree width quickly. Twenty Fourth Annual ACM Sympos. Theory Comput. (1992) (ACM Press, New York) 221–228Crossref, Google Scholar
• Reed B., Bailey R. Tree width and tangles: A new connectivity measure and some applications. Survey in Combinatorics (1997) (Cambridge University Press, Cambridge, U.K.) Crossref, Google Scholar
• Reinelt G. TSPLIB—A traveling salesman library. ORSA J. Comput. (1991) 3:376–384Link, Google Scholar
• Robertson N., Seymour P. Graph minors I: Excluding a forest. J. Combin. Theory, Ser. B (1983) 35:39–61Crossref, Google Scholar
• Robertson N., Seymour P. Graph minors III: Planar tree-width. J. Combin. Theory, Ser. B (1984) 36:49–64Crossref, Google Scholar
• Robertson N., Seymour P. Graph minors: A survey. Survey in Combinatorics (1985) (Cambridge University Press, Cambridge, U.K.) 153–171Crossref, Google Scholar
• Robertson N., Seymour P. Graph minors X: Obstructions to tree-decompositions. J. Combin. Theory, Ser. B (1991) 52:153–190Crossref, Google Scholar
• Robertson N., Seymour P. Graph minors XI: Circuits on a surface. J. Combin. Theory, Ser. B (1994) 60:72–106Crossref, Google Scholar
• Robertson N., Seymour P. Graph minors XIII: The disjoint paths problem. J. Combin. Theory, Ser. B (1995) 63:65–110Crossref, Google Scholar
• Seymour P., Thomas R. Graph searching and a min-max theorem for tree-width. J. Combin. Theory, Ser. B (1993) 58:22–33Crossref, Google Scholar
• Seymour P., Thomas R. Call routing and the ratcatcher. Combinatorica (1994) 14:217–241Crossref, Google Scholar
• Tamaki H. A linear time heuristic for the branch-decomposition of planar graphs. (2003) . Technical report MPI-I-2003-1-010, Max-Planck-Institut für Informatik, Saarbrücken, GermanyGoogle Scholar
• Telle J., Proskurowski A. Algorithms for vertex partitioning problems on partial k-trees. SIAM J. Discrete Math. (1997) 10:529–550Crossref, Google Scholar
• Thomas R. A Menger-like property of tree-width: The finite case. J. Combin. Theory, Ser. B (1990) 48:67–76Crossref, Google Scholar
• Wagner K. Über eine Eigenschaft der ebenen Komplexe. Mathematische Annalen (1937) 115:570–590Crossref, Google Scholar
• West D.Introduction to Graph Theory (2001) (Prentice-Hall, Upper Saddle River, NJ) Google Scholar