TRIANGULATING 3-COLORED GRAPHS IN LINEAR TIME AND LINEAR-SPACE

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.