TY - GEN
T1 - A simple Linear time algorithm for finding even triangulations of 2-connected bipartite plane graphs
AU - Zhang, Huaming
AU - He, Xin
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.
PY - 2002
Y1 - 2002
N2 - Recently, Hoffmann and Kriegel proved an important combinatorial theorem [4]: 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(n2) time algorithm was obtained in [4] for constructing an even triangulation of G. Hoffmann and Kriegel conjectured that there is an O(n3/2) algorithm for solving this problem [4]. 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.
AB - Recently, Hoffmann and Kriegel proved an important combinatorial theorem [4]: 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(n2) time algorithm was obtained in [4] for constructing an even triangulation of G. Hoffmann and Kriegel conjectured that there is an O(n3/2) algorithm for solving this problem [4]. 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.
UR - https://www.scopus.com/pages/publications/84938085220
U2 - 10.1007/3-540-45749-6_78
DO - 10.1007/3-540-45749-6_78
M3 - Conference contribution
AN - SCOPUS:84938085220
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 902
EP - 913
BT - Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings
A2 - Möhring, Rolf
A2 - Raman, Rajeev
PB - Springer Verlag
T2 - 10th Annual European Symposium on Algorithms, ESA 2002
Y2 - 17 September 2002 through 21 September 2002
ER -