×

zbMATH — the first resource for mathematics

A partial k-arboretum of graphs with bounded treewidth. (English) Zbl 0912.68148
Summary: The notion of treewidth has seen to be a powerful vehicle for many graph algorithmic studies. This survey paper wants to give an overview of many classes of graphs that can be seen to have a uniform upper bound on the treewidth of graphs in the class. Also, some mutual relations between such classes are discussed.

MSC:
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aggarwal, A.; Klawe, M.; Lichtenstein, D.; Linial, N.; Wigderson, A., A lower bound on the area of permutation layouts, Algorithmica, 6, 241-255, (1991) · Zbl 0711.68054
[2] Arnborg, S., Efficient algorithms for combinatorial problems on graphs with bounded decomposability — a survey, Bit, 25, 2-23, (1985) · Zbl 0573.68018
[3] Arnborg, S.; Corneil, D.G.; Proskurowski, A., Complexity of finding embeddings in a k-tree, SIAM J. algebra discrete methods, 8, 277-284, (1987) · Zbl 0611.05022
[4] Arnborg, S.; Courcelle, B.; Proskurowski, A.; Seese, D., An algebraic theory of graph reduction, J. ACM, 40, 1134-1164, (1993) · Zbl 0795.68156
[5] Arnborg, S.; Proskurowski, A., Characterization and recognition of partial 3-trees, SIAM J. algebra discrete methods, 7, 305-314, (1986) · Zbl 0597.05027
[6] Arnborg, S.; Proskurowski, A.; Corneil, D.G., Forbidden minors characterization of partial 3-trees, Discrete math., 80, 1-19, (1990) · Zbl 0701.05016
[7] Baker, B.S., Approximation algorithms for NP-complete problems on planar graphs, J. ACM, 41, 153-180, (1994) · Zbl 0807.68067
[8] Bauderon, M.; Courcelle, B., Graph expressions and graph rewritings, Mathematical systems theory, 20, 83-127, (1987) · Zbl 0641.68115
[9] Bern, M.W.; Lawler, E.L.; Wong, A.L., Linear time computation of optimal subgraphs of decomposable graphs, J. algorithms, 8, 216-235, (1987) · Zbl 0618.68058
[10] Bienstock, D., Graph searching, path-width, tree-width and related problems (a survey), DIMACS series in discrete mathematics and theoretical computer science, vol. 5, 33-49, (1991) · Zbl 0777.05090
[11] Bienstock, D.; Monma, C.L., On the complexity of covering vertices by faces in a planar graph, SIAM J. comput., 17, 53-76, (1988) · Zbl 0646.68085
[12] Bienstock, D.; Monma, C.L., On the complexity of embedding planar graphs to minimize certain distance measures, Algorithmica, 5, 93-109, (1990) · Zbl 0689.68044
[13] Bienstock, D.; Robertson, N.; Seymour, P.D.; Thomas, R., Quickly excluding a forest, J. combin. theory ser. B, 52, 274-283, (1991) · Zbl 0763.05023
[14] Bodlaender, H.L., Classes of graphs with bounded treewidth, () · Zbl 0684.68047
[15] Bodlaender, H.L., Dynamic programming algorithms on graphs with bounded tree-width, (), 105-119
[16] Bodlaender, H.L., Planar graphs with bounded treewidth, () · Zbl 0684.68047
[17] Bodlaender, H.L., Complexity of path-forming games, Theoret. comput. sci., 110, 215-245, (1993) · Zbl 0776.90100
[18] Bodlaender, H.L., On linear time minor tests with depth first search, J. algorithms, 14, 1-23, (1993) · Zbl 0764.68107
[19] Bodlaender, H.L., A tourist guide through treewidth, Acta cybernet., 11, 1-23, (1993) · Zbl 0804.68101
[20] Bodlaender, H.L., On disjoint cycles, Internat. J. found. comput. sci., 5, 59-68, (1994) · Zbl 0803.05030
[21] Bodlaender, H.L.; Engelfriet, J., Domino treewidth, J. algorithms, 24, 94-123, (1997) · Zbl 0882.68106
[22] Bodlaender, H.L.; Gilbert, J.R.; Hafsteinsson, H.; Kloks, T., Approximating treewidth, pathwidth, and minimum elimination tree height, J. algorithms, 18, 238-255, (1995) · Zbl 0818.68118
[23] Bodlaender, H.L.; Möhring, R.H., The pathwidth and treewidth of cographs, SIAM J. discrete methods, 6, 181-188, (1993) · Zbl 0773.05091
[24] Bodlaender, H.L.; Tan, R.B.; Thilikos, D.M.; van Leeuwen, J., On interval routing schemes and treewidth, (), 181-186
[25] Borie, R.; Gupta, A., Balanced decompositions for partial k-trees, (), 33-38 · Zbl 0803.05044
[26] Borie, R.B., Recursively constructed graph families, () · Zbl 0753.05062
[27] Borie, R.B.; Parker, R.G.; Tovey, C.A., Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families, Algorithmica, 7, 555-581, (1992) · Zbl 0753.05062
[28] Cattell, K.; Dinneen, M.J.; Fellows, M.R., A simple linear-time algorithm for finding path-decompositions of small width, manuscript, Inform. process. lett., 57, 197-204, (1996) · Zbl 0875.68699
[29] Chung, F.R.K., On the cutwidth and topological bandwidth of a tree, SIAM J. algebr. discrete methods, 6, 268-277, (1985) · Zbl 0565.05019
[30] Courcelle, B., Graph rewriting: an algebraic and logical approach, (), 192-242 · Zbl 0900.68282
[31] Courcelle, B., The monadic second-order logic of graphs I: recognizable sets of finite graphs, Inform. comput., 85, 12-75, (1990) · Zbl 0722.03008
[32] Courcelle, B., The monadic second-order logic of graphs III: treewidth, forbidden minors and complexity issues, Informatique théorique, 26, 257-286, (1992) · Zbl 0754.03006
[33] Courcelle, B.; Mosbah, M., Monadic second-order evaluations on tree-decomposable graphs, Theoret. comput. sci., 109, 49-82, (1993) · Zbl 0789.68083
[34] Dendris, N.D.; Kirousis, L.M.; Thilikos, D.M., Fugitive-search games on graphs and related parameters, Theoret. comput. sci., 172, 233-254, (1997) · Zbl 0903.68052
[35] Dolev, D.; Leighton, T.; Trickey, H., Planar embeddings of planar graphs, Adv. comput. res., 2, 53-76, (1984)
[36] Drewes, F.; Kreowski, H., A note on hyperedge replacement, (), 1-11, 1994 · Zbl 0765.68086
[37] Ellis, J.A.; Sudborough, I.H.; Turner, J., The vertex separation and search number of a graph, Inform. comput., 113, 50-79, (1994) · Zbl 0942.68641
[38] Fellows, M.R.; Langsten, M.A., Nonconstructive advances in polynomial-time complexity, Inform. process. lett., 26, 157-162, (1987) · Zbl 0637.68053
[39] Fellows, M.R.; Langston, M.A., On search, decision and the efficiency of polynomial-time algorithms, (), 501-512
[40] Gavril, F., The intersection graphs of subtrees in trees are exactly the chordal graphs, J. combin. theory ser. B, 16, 47-56, (1974) · Zbl 0266.05101
[41] Gilbert, J.R.; Hutchinson, J.P.; Tarjan, R.E., A separator theorem for graphs of bounded genus, J. algorithms, 5, 391-407, (1984) · Zbl 0556.05022
[42] Gilbert, J.R.; Rose, D.J.; Edenbrandt, A., A separator theorem for chordal graphs, SIAM J. algebras discrete methods, 5, 306-313, (1984) · Zbl 0551.05049
[43] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[44] Gorbunov, K.Y., An estimate of the tree-width of a graph which has not a given planar grid as a minor, (1993), manuscript
[45] Habel, A., Hyperedge replacement: grammars and languages, () · Zbl 0787.68066
[46] Habel, A.; Kreowski, H.J., May we introduce to you: hyperedge replacement, (), 15-26 · Zbl 0643.68106
[47] Hohberg, W.; Reischuk, R., Decomposition of graphs — a uniform approach for the design of fast sequential and parallel algorithms on graphs, (1989), preprint
[48] Hohberg, W.; Reischuk, R., A framework to design algorithms for optimization problems on graphs, (April 1990), preprint
[49] Hopcroft, J.E.; Paul, W.; Valiant, L., On time versus space, J. ACM, 24, 332-337, (1977) · Zbl 0358.68082
[50] Kaplan, H.; Shamir, R., Pathwidth, bandwidth and completion problems to proper interval graphs with small cliques, SIAM J. comput., 25, 540-561, (1996) · Zbl 0852.68072
[51] Kinnersley, N.G., The vertex separation number of a graph equals its path width, Inform. process. lett., 42, 345-350, (1992) · Zbl 0764.68121
[52] Kinnersley, N.G.; Langston, M.A., Obstruction set isolation for the gate matrix layout problem, Disc. appl. math., 54, 169-213, (1994) · Zbl 0941.68590
[53] Kirousis, L.M.; Papadimitriou, C.H., Interval graphs and searching, Discrete math., 55, 181-184, (1985) · Zbl 0566.05056
[54] Kirousis, L.M.; Papadimitriou, C.H., Searching and pebbling, Theoret. comput. sci., 47, 205-218, (1986) · Zbl 0616.68064
[55] T. Kloks, personal communication.
[56] Kloks, T., Treewidth. computations and approximations, () · Zbl 0825.68144
[57] Lagergren, J., The nonexistence of reduction rules giving an embedding into a k-tree, Discrete appl. math., 54, 219-223, (1994) · Zbl 0809.05034
[58] LaPaugh, A.S., Recontamination does not help to search a graph, J. ACM, 40, 224-245, (1993) · Zbl 0768.68048
[59] Lautemann, C., Decomposition trees: structured graph representation and efficient algorithms, (), 28-39
[60] Lingas, A., Subgraph isomorphism for easily separable graphs with bounded valence, (), 217-229
[61] Lipton, R.J.; Tarjan, R.E., A separator theorem for planar graphs, SIAM J. appl. math., 36, 177-189, (1979) · Zbl 0432.05022
[62] Liu, J.W.H., The role of elimination trees in sparse factorization, SIAM J. matrix anal. appl., 11, 134-172, (1990) · Zbl 0697.65013
[63] Makedon, F.S.; Papadimitriou, C.H.; Sudborough, I.H., Topological bandwidth, SIAM J. algebra discrete methods, 6, 418-444, (1985) · Zbl 0573.05052
[64] Möhring, R.H., Graph problems related to gate matrix layout and PLA folding, (), 17-51 · Zbl 0699.68072
[65] Möhring, R.H., Triangulating graphs without asteroidal triples, Disc. appl. math., 64, 281-287, (1996) · Zbl 0856.68112
[66] Mosbah, M.H., Constructions d’algorithmes pour LES graphes structurés par des Méthodes algébriques et logiques, ()
[67] Naumann, V., Measuring the distance to series-parallel graphs by path expressions, ()
[68] Ramachandramurthi, S., Algorithms for VLSI layout based on graph width metrics, ()
[69] N. Robertson, P.D. Seymour, Graph minors. XX. Wagner’s conjecture, in preparation. · Zbl 1061.05088
[70] Robertson, N.; Seymour, P.D., Graph minors. I. excluding a forest, J. combin. theory ser. B, 35, 39-61, (1983) · Zbl 0521.05062
[71] Robertson, N.; Seymour, P.D., Generalizing kuratowskis theorem, (), 129-138
[72] Robertson, N.; Seymour, P.D., Graph minors. III. planar tree-width, J. combin. theory ser. B, 36, 49-64, (1984) · Zbl 0548.05025
[73] Robertson, N.; Seymour, P.D., Graph width and well-quasi ordering: a survey, (), 399-406, Toronto
[74] Robertson, N.; Seymour, P.D., Graph minors — a survey, (), 153-171 · Zbl 0764.05069
[75] Robertson, N.; Seymour, P.D., Graph minors. II. algorithmic aspects of tree-width, J. algorithms, 7, 309-322, (1986) · Zbl 0611.05017
[76] Robertson, N.; Seymour, P.D., Graph minors. V. excluding a planar graph, J. combin. theory ser. B, 41, 92-114, (1986) · Zbl 0598.05055
[77] Robertson, N.; Seymour, P.D., Graph minors. VI. disjoint paths across a disc, J. combin. theory ser. B, 41, 115-138, (1986) · Zbl 0598.05042
[78] Robertson, N.; Seymour, P.D., Graph minors. VII. disjoint paths on a surface, J. combin. theory ser. B, 45, 212-254, (1988) · Zbl 0658.05044
[79] Robertson, N.; Seymour, P.D., Graph minors. IV. tree-width and well-quasi-ordering, J. combin. theory ser. B, 48, 227-254, (1990) · Zbl 0719.05032
[80] Robertson, N.; Seymour, P.D., Graph minors. IX. disjoint crossed paths, J. combin. theory ser. B, 49, 40-77, (1990) · Zbl 0741.05044
[81] Robertson, N.; Seymour, P.D., Graph minors. VIII. A Kuratowski theorem for general surfaces, J. combin. theory ser. B, 48, 255-288, (1990) · Zbl 0719.05033
[82] Robertson, N.; Seymour, P.D., Graph minors. X. obstructions to tree-decomposition, J. combin. theory ser. B, 52, 153-190, (1991) · Zbl 0764.05069
[83] Robertson, N.; Seymour, P.D., Graph minors, XV. giant steps, J. combin. theory ser. B, 68, 112-148, (1996) · Zbl 0860.05023
[84] Robertson, N.; Seymour, P.D., Graph minors. XVI. excluding a non-planar graph, (1991), manuscript · Zbl 1023.05040
[85] Robertson, N.; Seymour, P.D., Graph minors. XVII. taming a vortex, (1991), manuscript · Zbl 1027.05088
[86] Robertson, N.; Seymour, P.D., Graph minors. XXII. irrelevant vertices in linkage problems, (1992), manuscript · Zbl 1239.05173
[87] Robertson, N.; Seymour, P.D., Excluding a graph with one crossing, (), 669-675 · Zbl 0797.05038
[88] Robertson, N.; Seymour, P.D., Graph minors. XI. distance on a surface, J. combin. theory ser. B, 60, 72-106, (1994) · Zbl 0799.05016
[89] Robertson, N.; Seymour, P.D., Graph minors. XII. excluding a non-planar graph, J. combin. theory ser. B, 64, 240-272, (1995) · Zbl 0840.05016
[90] Robertson, N.; Seymour, P.D., Graph minors. XIII. the disjoint paths problem, J. combin. theory ser. B, 63, 65-110, (1995) · Zbl 0823.05038
[91] Robertson, N.; Seymour, P.D.; Thomas, R., Quickly excluding a planar graph, J. combin. theory ser. B, 62, 323-348, (1994) · Zbl 0807.05023
[92] Robertson, N.; Seymour, P.D., A survey of linkless embeddings, (), 125-136, Providence, RI · Zbl 0788.05034
[93] Rose, D.J., On simple characterization of k-trees, Discrete math., 7, 317-322, (1974) · Zbl 0285.05128
[94] Scheffler, P., Die baumweite von graphen als ein maß für die kompliziertheit algorithmischer probleme, () · Zbl 0684.68061
[95] Seese, D., Tree-partite graphs and the complexity of algorithms, (), 412-421 · Zbl 0574.68036
[96] Seymour, P.D.; Thomas, R., Graph searching and a minimax theorem for tree-width, J. combin. theory ser. B, 58, 239-257, (1993)
[97] Syslo, M.M., Characterisations of outerplanar graphs, Discrete math., 26, 47-53, (1979) · Zbl 0401.05040
[98] Takahashi, A.; Ueno, S.; Kajitani, Y., Minimal acyclic forbidden minors for the family of graphs with bounded path-width, Disc. math., 127, 293-304, (1994) · Zbl 0795.05123
[99] A. Takahashi, S. Ueno, Y. Kajitani, Mixed-searching and proper-path-width. · Zbl 0873.68148
[100] Thorup, M., Structured programs have small tree-width and good register allocation, (), 318-332 · Zbl 0890.68035
[101] van Leeuwen, J., Graph algorithms, (), 527-631, Amsterdam · Zbl 0900.68258
[102] van Leeuwen, J.; Tan, R.B., Compact routing methods: A survey, (), 71-93
[103] Vogler, W., On hyperedge replacement and BNLC graph grammars, Discrete appl. math., 46, 253-273, (1993) · Zbl 0789.68087
[104] Wimer, T.V., Linear algorithms on k-terminal graphs, () · Zbl 0669.05050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.