×

zbMATH — the first resource for mathematics

Minimal triangulations of graphs: a survey. (English) Zbl 1086.05069
Summary: Any given graph can be embedded in a chordal graph by adding edges, and the resulting chordal graph is called a triangulation of the input graph. In this paper we study minimal triangulations, which are the result of adding an inclusion minimal set of edges to produce a triangulation. This topic was first studied from the standpoint of sparse matrices and vertex elimination in graphs. Today we know that minimal triangulations are closely related to minimal separators of the input graph. Since the first papers presenting minimal triangulation algorithms appeared in 1976, several characterizations of minimal triangulations have been proved, and a variety of algorithms exist for computing minimal triangulations of both general and restricted graph classes. This survey presents and ties together these results in a unified modern notation, keeping an emphasis on the algorithms.

MSC:
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
Software:
symrcm
PDF BibTeX Cite
Full Text: DOI
References:
[1] Arikati, S.; Rangan, P., An efficient algorithm for finding a two-pair, and its applications, Discrete appl. math., 31, 71-74, (1991) · Zbl 0748.05085
[2] Arnborg, S.; Corneil, D.G.; Proskurowski, A., Complexity of finding embeddings in a \(k\)-tree, SIAM J. algebraic discrete methods, 8, 277-284, (1987) · Zbl 0611.05022
[3] Balas, E., A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring, Discrete appl. math., 15, 123-134, (1986) · Zbl 0633.05039
[4] Beeri, C.; Fagin, R.; Maier, D.; Yannakakis, M., On the desirability of acyclic database systems, J. assoc. comput. Mach., 30, 479-513, (1983) · Zbl 0624.68087
[5] A. Berry, Désarticulation d’un graphe, Ph.D. Thesis, LIRMM, Montpellier, France, 1998.
[6] Berry, A., A wide-range efficient algorithm for minimal triangulation, (), S860-S861
[7] Berry, A.; Blair, J.R.S.; Heggernes, P.; Peyton, B.W., Maximum cardinality search for computing minimal triangulations of graphs, Algorithmica, 39, 4, 287-298, (2004) · Zbl 1090.68080
[8] Berry, A.; Bordat, J.-P., Separability generalizes Dirac’s theorem, Discrete appl. math., 84, 43-53, (1998) · Zbl 0901.05079
[9] Berry, A.; Bordat, J.P.; Cogis, O., Generating all the minimal separators of a graph, Internat. J. foundations comput. sci., 11, 3, 397-403, (2000) · Zbl 1320.05120
[10] Berry, A.; Bordat, J.-P.; Heggernes, P.; Simonet, G.; Villanger, Y., A wide-range algorithm for minimal triangulation from an arbitrary ordering, J. algorithms, 58, 1, 33-66, (2006) · Zbl 1093.68137
[11] A. Berry, P. Heggernes, G. Simonet, The minimum degree heuristic and the minimal triangulation process, Proceedings of the 29th Workshop on Graph Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 2880, Springer, Berlin, 2003, pp. 58-70. · Zbl 1255.05186
[12] A. Berry, P. Heggernes, Y. Villanger, A vertex incremental approach for dynamically maintaining chordal graphs, in: Algorithms and Computation—ISAAC 2003, Lecture Notes in Computer Science, vol. 2906, Springer, Berlin, 2003, pp. 47-57. · Zbl 1205.68256
[13] Blair, J.R.S.; Heggernes, P.; Telle, J.A., A practical algorithm for making filled graphs minimal, Theoret. comput. sci., 250, 125-141, (2001) · Zbl 0952.68104
[14] J.R.S. Blair, B.W. Peyton, An introduction to chordal graphs and clique trees, in: J.A. George, J.R. Gilbert, J.W.H. Liu (Eds.), Sparse matrix computations: graph theory issues and algorithms, IMA Volumes in Mathematics and its Applications, vol. 56, Springer, Berlin, 1993, pp. 1-30. · Zbl 0803.68081
[15] Bodlaender, H.L., A tourist guide through treewidth, Acta cybernet., 11, 1-21, (1993) · Zbl 0804.68101
[16] Bodlaender, H.L.; Kloks, T.; Kratsch, D.; Müller, H., Treewidth and minimum fill-in on \(d\)-trapezoid graphs, J. graph alg. appl., 2, 1-23, (1998) · Zbl 0905.68101
[17] H.L. Bodlaender, A.M.C.A. Koster, Safe separators for treewidth, Technical Report UU-CS-2003-027, Institute of Information and Computing Sciences, Utrecht University, Netherlands, 2002. · Zbl 1084.05065
[18] Bornstein, C.F.; Maggs, B.M.; Miller, G.L., Tradeoffs between parallelism and fill in nested dissection, (), 191-200
[19] Bouchitté, V.; Todinca, I., Treewidth and minimum fill in: grouping the minimal separators, SIAM J. comput., 31, 212-232, (2001) · Zbl 0987.05085
[20] Bouchitté, V.; Todinca, I., Listing all potential maximal cliques of a graph, Theoret. comput. sci., 276, 1-2, 17-32, (2002) · Zbl 1002.68104
[21] Broersma, H.J.; Dahlhaus, E.; Kloks, T., A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs, Discrete appl. math., 99, 367-400, (2000) · Zbl 0940.05064
[22] Buneman, P., A characterization of rigid circuit graphs, Discrete math., 9, 205-212, (1974) · Zbl 0288.05128
[23] Cai, L., Fixed-parameter tractability of graph modification problems for hereditary properties, Inform. process. lett., 58, 4, 171-176, (1996) · Zbl 0875.68702
[24] Chandrasekharan, N.; Iyengar, S.S., NC algorithms for recognizing chordal graphs and \(k\)-trees, IEEE trans. comput., 37, 10, 1178-1183, (1988) · Zbl 0658.68080
[25] Chung, F.R.K.; Mumford, D., Chordal completions of planar graphs, J. combin. theory, 31, 96-106, (1994) · Zbl 0809.05038
[26] Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progressions, J. symbolic comput., 9, 1-6, (1990) · Zbl 0702.65046
[27] Corneil, D.G.; Olariu, S.; Stewart, L., Asteroidal triple-free graphs, SIAM J. discrete math., 10, 399-430, (1997) · Zbl 0884.05075
[28] Dahlhaus, E., The parallel complexity of elimination ordering procedures, (), 225-236
[29] E. Dahlhaus, Minimal elimination ordering inside a given chordal graph, in: Graph Theoretical Concepts in Computer Science—WG’97, Lecture Notes in Computer Science, vol. 1335, Springer, Berlin, 1997, pp. 132-143. · Zbl 0886.05103
[30] E. Dahlhaus, Minimal elimination of planar graphs, in: S. Arnborg, L. Ivansson (Eds.), Algorithm Theory—SWAT 1998, Lecture Notes in Computer Science, vol. 1432, Springer, Berlin, 1998, pp. 210-221.
[31] E. Dahlhaus, An improved linear time algorithm for minimal elimination ordering in planar graphs that is parallelizable, Technical report TR-465-99, ALCOM-IT European Union ESPRIT LTR Project 20244, 1999.
[32] E. Dahlhaus, Converting a Nested Dissection into a minimal elimination ordering efficiently, 2000, unpublished manuscript.
[33] Dahlhaus, E., Minimal elimination ordering for graphs of bounded degree, Discrete appl. math., 116, 127-143, (2002) · Zbl 0998.05061
[34] Dahlhaus, E.; Karpinski, M., An efficient parallel algorithm for the minimal elimination ordering of an arbitrary graph, Theoret. comput. sci., 134, 2, 493-528, (1994) · Zbl 0938.68958
[35] Dahlhaus, E.; Karpinski, M.; Novick, M., Fast parallel algorithms for the clique separator decomposition, () · Zbl 0800.68623
[36] Dearing, P.M.; Shier, D.R.; Warner, D.D., Maximal chordal subgraphs, Discrete appl. math., 20, 181-190, (1988) · Zbl 0664.05032
[37] Dirac, G.A., On rigid circuit graphs, Anh. math. sem. univ. Hamburg, 25, 71-76, (1961) · Zbl 0098.14703
[38] Edenbrandt, A., Chordal graph recognition is in NC, Inform. process. lett., 24, 239-241, (1987) · Zbl 0653.68035
[39] F.V. Fomin, D. Kratsch, I. Todinca, Exact (exponential) algorithms for treewidth and minimum fill-in, in: Automata, Languages and Programming—ICALP 2004, Lecture Notes in Computer Science, vol. 3142, Springer, Berlin, 2004, pp. 568-580. · Zbl 1099.68076
[40] Fulkerson, D.R.; Gross, O.A., Incidence matrices and interval graphs, Pacific J. math., 15, 835-855, (1965) · Zbl 0132.21001
[41] Garey, M.R.; Johnson, D.S., Computers and intractability, (1978), Freeman · Zbl 0379.68035
[42] 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
[43] George, J.A., Nested dissection of a regular finite element mesh, SIAM J. numer. anal., 10, 345-363, (1973) · Zbl 0259.65087
[44] George, J.A.; Liu, J.W.H., Computer solution of large sparse positive definite systems, (1981), Prentice-Hall Englewood Cliffs, New Jersey
[45] Goldberg, P.W.; Golumbic, M.C.; Kaplan, H.; Shamir, R., Four strikes against physical mapping of DNA, J. comput. biol., 2, 1, 139-152, (1995)
[46] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press · Zbl 0541.05054
[47] Golumbic, M.C.; Monma, C.L.; Trotter, W.T., Tolerance graphs, Discrete appl. math., 9, 2, 157-170, (1984) · Zbl 0547.05054
[48] A. Hajnal, J. Surányi, Über die Ausflösung von Graphen in vollständige Teilgraphen, Ann. Univ. Sci. Budapest (1958) 113-121. · Zbl 0093.37801
[49] Heggernes, P.; Eisenstat, S.; Kumfert, G.; Pothen, A., The computational complexity of the minimum degree algorithm, (), 98-109, Also available as ICASE Report 2001-42, NASA/CR-2001-211421, NASA Langley Research Center, USA
[50] Heggernes, P.; Telle, J.A.; Villanger, Y., Computing minimal triangulations in time \(O(n^\alpha \log n) = \operatorname{o}(n^{2.376})\), SIAM J. disc. math., 19, 4, 900-913, (2005) · Zbl 1105.05066
[51] P. Heggernes, Y. Villanger, Efficient implementation of a minimal triangulation algorithm, in: Algorithms—ESA 2002, Lecture Notes in Computer Science, vol. 2461, Springer, Berlin, 2002, pp. 550-561. · Zbl 1019.68809
[52] Ho, C.W.; Lee, R.C.T., Counting clique trees and computing perfect elimination schemes in parallel, Inform. process. lett., 31, 61-68, (1989) · Zbl 0685.68050
[53] Ibarra, L., Fully dynamic algorithms for chordal graphs, () · Zbl 0929.68087
[54] Kaplan, H.; Shamir, R.; Tarjan, R.E., Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs, SIAM J. comput., 28, 5, 1906-1922, (1999) · Zbl 0928.68124
[55] T. Kloks, H.L. Bodlaender, H. Müller, D. Kratsch, Computing treewidth and minimum fill-in: all you need are the minimal separators, in: T. Lengauer (Ed.), Algorithms—ESA 1993, Lecture Notes in Computer Science, vol. 726, Springer, Berlin, 1993, pp. 260-271.
[56] T. Kloks, H.L. Bodlaender, H. Müller, D. Kratsch, Erratum to ESA 1993 proceedings, in: Algorithms—ESA 1994, Lecture Notes in Computer Science, vol. 855, Springer, Berlin, 1994, p. 508.
[57] Kloks, T.; Kratsch, D., Listing all minimal separators of a graph, SIAM J. comput., 27, 3, 605-613, (1998) · Zbl 0907.68136
[58] Kloks, T.; Kratsch, D.; Müller, H., On the structure of graphs with bounded asteroidal number, Graphs combin., 17, 295-306, (2001) · Zbl 0989.05059
[59] Kloks, T.; Kratsch, D.; Spinrad, J., On treewidth and minimum fill-in of asteroidal triple-free graphs, Theoret. comput. sci., 175, 309-335, (1997) · Zbl 0903.68139
[60] D. Kratsch, J. Spinrad, Minimal fill in \(\operatorname{o}(n^3)\) time, Discrete Math. in press, 10.1016/j.disc.2005.12.009. · Zbl 1084.05070
[61] Kratsch, D.; Stewart, L., Domination on cocomparability graphs, SIAM J. discrete math., 6, 3, 400-417, (1993) · Zbl 0780.05032
[62] Lauritzen, S.L.; Spiegelhalter, D.J., Local computations with probabilities on graphical structures and their applications to expert systems, J. roy. statist. soc. ser B, 50, 157-224, (1988) · Zbl 0684.68106
[63] Lekkerkerker, C.G.; Boland, J.C., Representation of a finite graph by a set of intervals on the real line, Fund. math., 51, 45-64, (1962) · Zbl 0105.17501
[64] Liu, J.W.H., Equivalent sparse matrix reorderings by elimination tree rotations, SIAM J. sci. statist. comput., 9, 3, 424-444, (1988) · Zbl 0651.65016
[65] Liu, J.W.H., The role of elimination trees in sparse factorization, SIAM J. matrix anal. appl., 11, 1, 134-172, (1990) · Zbl 0697.65013
[66] McConnell, R.M.; Spinrad, J.P., Modular decomposition and transitive orientation, Discrete appl. math., 201, 1-3, 189-241, (1999) · Zbl 0933.05146
[67] D. Meister, Recognizing and computing minimal triangulations efficiently, Technical Report 302, Julius Maximilians Universität Würzburg, 2002.
[68] Möhring, R.H., Triangulating graphs without asteroidal triples, Discrete appl. math., 64, 281-287, (1996) · Zbl 0856.68112
[69] Naor, J.; Naor, M.; Schäffer, A., Fast parallel algorithms for chordal graphs, (), 355-364
[70] Natanzon, A.; Shamir, R.; Sharan, R., A polynomial approximation algorithm for the minimum fill-in problem, SIAM J. computing, 30, 1067-1079, (2000) · Zbl 0969.68194
[71] Natanzon, A.; Shamir, R.; Sharan, R., Complexity classification of some edge modification problems, Discrete appl. math., 113, 109-128, (2001) · Zbl 0982.68104
[72] Ohtsuki, T., A fast algorithm for finding an optimal ordering in the vertex elimination on a graph, SIAM J. comput., 5, 133-145, (1976) · Zbl 0353.65018
[73] Ohtsuki, T.; Cheung, L.K.; Fujisawa, T., Minimal triangulation of a graph and optimal pivoting ordering in a sparse matrix, J. math. anal. appl., 54, 622-633, (1976) · Zbl 0371.65006
[74] Parra, A.; Scheffler, P., Characterizations and algorithmic applications of chordal graph embeddings, Discrete appl. math., 79, 171-188, (1997) · Zbl 0887.05044
[75] Parter, S., The use of linear graphs in Gauss elimination, SIAM rev., 3, 119-130, (1961) · Zbl 0102.11302
[76] Peyton, B.W., Minimal orderings revisited, SIAM J. matrix anal. appl., 23, 1, 271-294, (2001) · Zbl 1044.65035
[77] Robertson, N.; Seymour, P., Graph minors II. algorithmic aspects of tree-width, J. algorithms, 7, 309-322, (1986) · Zbl 0611.05017
[78] Rose, D.J., A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations, (), 183-217
[79] Rose, D.; Tarjan, R.E.; Lueker, G., Algorithmic aspects of vertex elimination on graphs, SIAM J. comput., 5, 146-160, (1976)
[80] Tarjan, R.E.; Yannakakis, M., Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. comput., 13, 566-579, (1984) · Zbl 0545.68062
[81] Y. Villanger, Lex M versus MCS-M, Technical Report, University of Bergen, Norway, 2003.
[82] J.R. Walter. Representations of rigid cycle graphs, Ph.D. Thesis, Wayne State University, 1972.
[83] Xue, J., Edge-maximal triangulated subgraphs and heuristics for the maximum clique problem, Networks, 24, 109-120, (1994) · Zbl 0791.90065
[84] Yannakakis, M., Computing the minimum fill-in is NP-complete, SIAM J. algebraic discrete methods, 2, 77-79, (1981) · Zbl 0496.68033
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.