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 networkG=(V, E), with a source and a sink, such that an edgee=uv inE is labeled u, v or u, u (or both) depending on the existence of a (simple) path from the source to the sink traversinge, that visits the verticesu andv in the orderu, v orv, u respectively. The best-known algorithm for this problem requiresO(¦V¦·¦E¦) time [5]. We show that the problem is solvable optimally on a planar graph.