CIRCULARITY OF PLANAR GRAPHS
Richard H. Hammack, Klaus Kaiser · 1999
Abstract. A circular cover of a graph G is a cover {X0, · · · , Xn−1} of the topological space G by closed connected subsets, indexed over Zn, with the following properties: Each element in the cover contains a vertex of G, each vertex of G is contained in at most two elements of the cover, and Xa ∩ Xb 6 = ∅ if and only if b − a ∈ {−1, 0, 1}. The circularity of G is the largest integer n for which there is a circular cover of G with n elements. It is known that the circularity of a planar graph is even. We sharpen this result by proving that the circularity of a plane graph is twice the maximum number of disjoint paths joining two faces of G. This result leads to a polynomial-time algorithm which computes the circularity of any connected planar graph. 1.