A linear algorithm for the all-bidirectional-edges problem on planar graphs

The all-bidirectional-edges problem is to find an edge-labeling of an undirected network G=(V, E), with a source and a sink, such that an edge e=uv in E is labeled 〈u, v〉 or 〈u, u〉 (or both) depending on the existence of a (simple) path from the source to the sink traversing e, that visits the vertices u and v in the order u, v or v, u respectively. The best-known algorithm for this problem requires O(|V|·|E|) time [5]. We show that the problem is solvable optimally on a planar graph. © 1993 Springer-Verlag New York Inc.