NP-Completeness of st-orientations for plane graphs

An st-orientation or bipolar orientation of a 2-connected graph G is an orientation of its edges to generate a directed acyclic graph with a single source s and a single sink t. Given a plane graph G and two exterior vertices s and t, the problem of finding an optimum st-orientation, i.e., an st-orientation in which the length of a longest st-path is minimized, was first proposed indirectly by Rosenstiehl and Tarjan in and then later directly by He and Kao in . In this paper, we prove that, given a 2-connected plane graph G, two exterior vertices s, t, and a positive integer K, the decision problem of whether G has an st-orientation, where the maximum length of an st-path is ≤K, is NP-Complete. This solves a long standing open problem on the complexity of optimum st-orientations for plane graphs. As a by-product, we prove that the NP-Completeness result holds for planar graphs as well.