Rm. Idury et Aa. Schaffer, TRIANGULATING 3-COLORED GRAPHS IN LINEAR TIME AND LINEAR-SPACE, SIAM journal on discrete mathematics, 6(2), 1993, pp. 289-293
Kannan and Warnow [Triangulating Three-Colored Graphs, Proc. 2nd SODA,
1991, pp. 337-343 and SIAM J. Discrete Math., 5 (1992), pp. 249-258]
describe an algorithm to decide whether a three-colored graph can be t
riangulated so that all the edges connect vertices of different colors
. This problem is motivated by a problem in evolutionary biology. Kann
an and Warnow have two implementation strategies for their algorithm:
one uses slightly superlinear time, while the other uses linear time b
ut quadratic space. We note that three-colored triangulatable graphs a
re always planar, and we use this fact to modify Kannan and Warnow's a
lgorithm to obtain an algorithm that uses both linear time and linear
space.