A separator theorem for chordal graphs. (English) Zbl 0551.05049

A graph is called chordal if every cycle of it of length at least four has a chord. In the paper it is proved: Let G be a chordal graph with n vertices and m edges. Then G has a set of O(\(\sqrt{m})\) vertices whose removal leaves no connected component with more than n/2 vertices. Moreover, an O(m) time algorithm for finding the separating set is presented.
Reviewer: P.Horak


05C40 Connectivity
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI Link


[1] Properties of acyclic database schemesProc. 13th Annual ACM Symposium on Theory of Computing1981355362
[2] Dirac, G. A., On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg, 25, 71, (1961) · Zbl 0098.14703
[3] Djidjev, HristoNicolov, On the problem of partitioning planar graphs, SIAM J. Algebraic Discrete Methods, 3, 229, (1982) · Zbl 0503.05057
[4] Fulkerson, D. R.; Gross, O. A., Incidence matrices and interval graphs, Pacific J. Math., 15, 835, (1965) · Zbl 0132.21001
[5] Ph.D. ThesisGraph separator theorems and sparse Gaussian eliminationStanford UniversityStanford, CA1980
[6] Gilbert, JohnR.; Hutchinson, JoanP.; Tarjan, RobertEndre, A separator theorem for graphs of bounded genus, J. Algorithms, 5, 391, (1984) · Zbl 0556.05022
[7] Hajnal, András; Surányi, János, Über die auflösung von graphen in vollständige teilgraphen, Ann. Univ. Sci. Budapest. Eötvös. Sect. Math., 1, 113, (1958) · Zbl 0093.37801
[8] Jordan, Camille, Sur LES assemblages de lignes, Journal Reine Angew. Math., 70, 185, (1869)
[9] A layout for the shuffle-exchange networkTechnical reportCMU-CS-80-139Carnegie-Mellon Univ. Department of Computer SciencePittsburgh, PA1980
[10] New lower bound techniques for VLSIProc. 22nd Annual IEEE Symposium on Foundations of Computer Science1981112
[11] Area-efficient graph layouts (for VLSI)Proc. 21st Annual IEEE Symposium on Foundations of Computer Science1980270281 · Zbl 1392.68055
[12] Memory bounds for the recognition of context-free and context-sensitive languagesIEEE Conference Record on Switching Theory and Logical Design1965191202
[13] Lipton, RichardJ.; Rose, DonaldJ.; Tarjan, RobertEndre, Generalized nested dissection, SIAM J. Numer. Anal., 16, 346, (1979) · Zbl 0435.65021 · doi:10.1137/0716027
[14] Lipton, RichardJ.; Tarjan, RobertEndre, Applications of a planar separator theorem, SIAM J. Comput., 9, 615, (1980) · Zbl 0456.68077 · doi:10.1137/0209046
[15] Lipton, RichardJ.; Tarjan, RobertEndre, A separator theorem for planar graphs, SIAM J. Appl. Math., 36, 177, (1979) · Zbl 0432.05022 · doi:10.1137/0136016
[16] Rose, DonaldJ.; Read, R. C., A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations, Graph theory and computing, 183, (1972), Academic Press, New York · Zbl 0266.65028
[17] Rose, DonaldJ., On simple characterizations of {\it k}-trees, Discrete Math., 7, 317, (1974) · Zbl 0285.05128 · doi:10.1016/0012-365X(74)90042-9
[18] Rose, DonaldJ., Triangulated graphs and the elimination process, J. Math. Anal. Appl., 32, 597, (1970) · Zbl 0216.02602
[19] Rose, DonaldJ.; Tarjan, R. Endre; Lueker, GeorgeS., Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., 5, 266, (1976) · Zbl 0353.65019 · doi:10.1137/0205021
[20] Yannakakis, Mihalis, Computing the minimum fill-in is NP-complete, SIAM J. Algebraic Discrete Methods, 2, 77, (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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.