NP-Completeness of st-orientations for plane graphs
Sadish Sadasivam and Huaming Zhang
Abstract
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
vertices s and t on the exterior face of G, the problem of finding an
optimum st-orientation, i.e., an st-orientation in which the length of
the longest st-path is minimized, was first proposed indirectly by
Rosenstiehl and Tarjan and then later directly by He and Kao. In this
paper, we prove that, given a 2-connected plane graph G, two vertices s,
t, on the exterior face of G 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.