Triangulating Three-Colored Graphs in Linear Time and Linear Space
Ramana M. Idury, Alejandro A. Schäffer · SIAM Journal on Discrete Mathematics · 1993
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 triangulated so that all the edges connect vertices of different colors. This problem is motivated by a problem in evolutionary biology. Kannan and Warnow have two implementation strategies for their algorithm: one uses slightly superlinear time, while the other uses linear time but quadratic space. We note that three-colored triangulatable graphs are always planar, and we use this fact to modify Kannan and Warnow’s algorithm to obtain an algorithm that uses both linear time and linear space.