Planar oriented graphs of diameter two

Abstract

Chvátal and Thomassen (J. Combinatorial Theory Ser. B 24 (1978) 61-75) proved that, given a 2-edge-connected graph G., the problem of deciding whether G has an orientation of diameter 2 is NP-complete. In this note we show that this problem, if restricted to planar graphs, becomes simple. We show that only two planar graphs admit a strong orientation of diameter 2: the 3-cycle and the octahedron.