Abstract
A chordal graph H is a triangulation of a graph G, if H is obtained by adding edges to G. If no proper subgraph of H is a triangulation of G, then H is a minimal triangulation of G. A potential maximal clique of G is a set of vertices that induces a maximal clique in a minimal triangulation of G. We will characterise the potential maximal cliques of permutation graphs and give a characterisation of minimal triangulations of permutation graphs in terms of sets of potential maximal cliques. This results in linear-time algorithms for computing treewidth and minimum fill-in for permutation graphs.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM Journal on Algebraic and Discrete Methods 8, 277–284 (1987)
Bodlaender, H.L., Kloks, T., Kratsch, D.: Treewidth and Pathwidth of Permutation Graphs. SIAM Journal on Discrete Mathematics 8(4), 606–616 (1995)
Bodlaender, H.L., Kloks, T., Kratsch, D., Müller, H.: Treewidth and minimum fill-in on d-trapezoid graphs. Journal of Graph Algorithms and Applications 2(3), 1–23 (1998)
Bodlaender, H.L., Möhring, R.H.: The pathwidth and treewidth of cographs. SIAM Journal on Discrete Mathematics 6, 181–188 (1993)
Bouchitté, V., Todinca, I.: Treewidth and Minimum Fill-in: Grouping the Minimal Separators. SIAM Journal on Computing 31, 212–232 (2001)
Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pacific Journal of Mathematics 15, 835–855 (1965)
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)
Kloks, T., Kratsch, D., Spinrad, J.: On treewidth and minimum fill-in of asteroidal triple-free graphs. Theoretical Computer Science 175, 309–335 (1997)
Lekkerkerker, C.G., Boland, J.C.: Representation of finite graphs by a set of intervals on the real line. Fundamenta Mathematicae 51, 45–64 (1962)
Möhring, R.H.: Triangulating graphs without asteroidal triples. Discrete Applied Mathematics 64, 281–287 (1996)
Parra, A., Scheffler, P.: How to Use the Minimal Separators of a Graph for its Chordal Triangulation. In: Fülöp, Z., Gecseg, F. (eds.) ICALP 1995. LNCS, vol. 944, pp. 123–134. Springer, Heidelberg (1995)
Parra, A., Scheffler, P.: Characterizations and algorithmic applications of chordal graph embeddings. Discrete Applied Mathematics 79, 171–188 (1997)
Rose, D.J.: Triangulated Graphs and the Elimination Process. Journal of Mathematical Analysis and Applications 32, 597–609 (1970)
Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM Jounal on Computing 5, 266–283 (1976)
Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM Journal on Algebraic and Discrete Methods 2, 77–79 (1981)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Meister, D. (2005). Computing Treewidth and Minimum Fill-In for Permutation Graphs in Linear Time. In: Kratsch, D. (eds) Graph-Theoretic Concepts in Computer Science. WG 2005. Lecture Notes in Computer Science, vol 3787. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11604686_9
Download citation
DOI: https://doi.org/10.1007/11604686_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-31000-6
Online ISBN: 978-3-540-31468-4
eBook Packages: Computer ScienceComputer Science (R0)