AbstractWe apply Lekkerkerker and Boland's recognition algorithm for triangulated graphs to the class of weakly triangulated graphs. This yields a new characterization of weakly triangulated graphs, as well as a new O(m2) recognition algorithm which, unlike the previous ones, is not based on the notion of a 2-pair, but rather on the structural properties of the minimal separators of the graph. It also gives the strongest relationship to the class of triangulated graphs that has been established so far.
Categories and Subject Descriptors: G.2.2 [Discrete Mathematics]: Graph Theory; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems
Additional Key Words and Phrases: weakly triangulated graphs, graph recognition, graph characterization, minimal separators, triangulated graphs
Selected references
- Donald J. Rose, R. Endre Tarjan, and George S. Lueker. Algorithmic aspects of vertex elimination on graphs. SIAM Journal on Computing, 5(2):266-283, June 1976.
- Jeremy P. Spinrad. Finding largest holes. Information Processing Letters, 39(4):227-229, 30 August 1991.