A Simple Linear Time Algorithm for Finding Even Triangulations of 2-Connected Bipartite Plane Graphs

摘要

Recently, Hoffmann and Kriegel proved an important combinatorial theorem: Every 2-connected bipartite plane graph G has a triangulation in which all vertices have even degree (it's called an even triangulation). Combined with a classical Whitney's Theorem, this result implies that every such a graph has a 3-colorable plane triangulation. Using this result, Hoffmann and Kriegel significantly improved the upper bounds of several art gallery and prison guard problems. A complicated O(n~2) time algorithm was obtained in [4] for constructing an even triangulation of G. Hoffmann and Kriegel conjectured that there is an O(n~(3/2)) algorithm for solving this problem. In this paper, we develop a very simple O(n) time algorithm for solving this problem. Our algorithm is based on thorough study of the structure of all even triangulations of G. We also obtain a simple formula for computing the number of distinct even triangulations of G.