We show the first a(n~2) algorithm for coloring vertices of triangle-free planar graphs using three colors. The time complexity of the algorithm is O(nlogn). Our approach can be also used to design O(npolylogn)-time algorithms for two other similar coloring problems. A remarkable ingredient of our algorithm is the data structure processing short path queries introduced recently in [9]. In this paper we show how to adapt it to the fully dynamic environment where edge insertions and deletions are allowed.
展开▼
