Let G denote a directed planar graph of order n with real edge weights and no negative cycles, and let Gˆ denote an embedding of G in the plane. A face-on-vertex covering (FOVC) of Gˆ is a set of faces of Gˆ that cover all vertices of G. Let p denote the minimum cardinality of any FOVC over all embeddings of G. This paper describes a method of computing all pairs shortest path data for G in time O(pn). The shortest path data are encoded into routing tables, which are based on a naming of the vertices of G with distinct integers in [1,n]. For each vertex v, these tables give the label of each arc vw, that is, a list of ranges of names of vertices, each of which has a shortest path from v that begins with arc vw.
The method breaks down into two main phases. The first phase takes O(n) time to find an embedding Gˆ of G and an FOVC of Gˆ that is of cardinality q ≤ 4p. This phase uses a generic algorithm for NP-hard problems that, given an embedding Gˆ, yields an FOVC of cardinality less than twice that of a minimum-cardinality FOVC of Gˆ.
The second phase generates routing tables for G based on a given embedding Gˆ and corresponding FOVC of cardinality q. This phase consists of five main steps:
Name the vertices of G in clockwise order around each face of the FOVC. This step requires O(n) time.
Decompose Gˆ into q hammocks (subgraphs of G consisting of exactly two disjoint simple paths together with additional edges joining vertices in one path to vertices in the other). Each hammock has exactly four attachment vertices (the ends of the two paths) that connect it to the rest of G. This step requires O(n) time.
Compute the shortest paths between every pair of attachment vertices, using a technique for hammock compression and the monotonicity of a certain distance function over the faces of a planar graph. This step requires O(q2) time.
Using the shortest path data for attachment vertices, compute routing tables for all shortest paths from vertices in one hammock to vertices in another. This step requires O(qn) time.
Employing an algorithm to compute shortest paths in outer planar graphs (those for which q =1), and making use of deques with heap order, compute routing tables for all shortest paths between vertices in a single hammock. This step requires O(n) time.
For anyone interested in planar graphs or shortest path problems, this paper is important. It combines many new insights with a variety of results that have appeared over the last decade to produce a lengthy and intricate algorithm of major theoretical interest. The paper is not easy to read, but the exposition is well organized and, with one or two minor lapses, clear. Examples and figures are used to good effect.
