Remote host: pollux.cse.buffalo.edu ### Begin Citation ### Do not delete this line ### %A Zhang, Huaming %A He, Xin %T On Even Triangulations of 2-Connected Embedded Graphs %R 2002-13 %D July 06, 2002 %I Department of Computer Science and Engineering, SUNY Buffalo %X Recently, Hoffmann and Kriegel proved an important combinatorial theorem [HK96]: 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 theorem, 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 [HK96] for constructing an even triangulation of G. Hoffmann and Kriegel conjectured that there is an O(n^{3/2}) time algorithm for solving this problem. In this paper, we develop a simple proof of the above theorem. Our proof reveals and relies on a natural correspondence between even triangulations of $G$ and certain orientations of G. Based on this new proof, we obtain a very simple O(n) time algorithm for finding an even triangulation of G. We also extend our proof to show the existence of even triangulations for similar graphs on high genus surface.