Spanning closed walks and TSP in 3-connected planar graphs

In this paper, we prove the following theorem, which is motivated by two different contexts independently, namely graph theory and combinatorial optimization. Given a circuit graph (which is obtained from a 3-connected planar graph by deleting one vertex) with n vertices, there is a spanning closed walk W   of length at most 4(n−1)/34(n−1)/3 such that each edge is used by W at most twice.Our proof is constructive (and purely combinatorial) in the sense that there is an O(n2)O(n2)-time algorithm to construct such a walk in a given 3-connected planar graph. We shall construct an example that shows that the upper bound 4(n−1)/34(n−1)/3 is essentially tight. We also point out that 2-connected planar graphs may not have such a walk, as K2,n−2K2,n−2 shows.