Path and Intersections: Characterization of Quasi-metrics in Directed Okamura-Seymour Instances

We study the following distance realization problem. Given a quasi-metric D on a set T of terminals, does there exist a directed Okamura-Seymour graph that realizes D as the (directed) shortest-path distance metric on T? We show that, if we are further given the circular ordering of terminals lying on the boundary, then Monge property is a sufficient and necessary condition. This generalizes previous results for undirected Okamura-Seymour instances. With the circular ordering, we give a greedy algorithm for constructing a directed Okamura-Seymour instance that realizes the input quasi-metric. The algorithm takes the dual perspective concerning flows and routings, and is based on a new way of analyzing graph structures, by viewing graphs as paths and their intersections. We believe this new understanding is of independent interest and will prove useful in other problems in graph theory and graph algorithms. We also design an efficient algorithm for finding such a circular ordering that makes D satisfy Monge property, if one exists. Combined with our result above, this gives an efficient algorithm for the distance realization problem.