An optimal fault-tolerant routing for triconnected planar graphs (Q4944980)

This paper is devoted to the problem of constructing fault-tolerant routings for a communication network. The surviving route graph for a graph \(G\), a routing \(\rho\) and a set of faults \(F\) is a directed graph consisting of nonfaulty nodes, with a directed edge from a node \(x\) to a node \(y\) iff there are no faults on the route from \(x\) to \(y\). The diameter of the surviving route graph could be one of the fault-tolerant measures from the graph \(G\) and the routing \(\rho\). The authors show that they can construct a routing for every triconnected planar graph with a triangle face such that the diameter of the surviving route graph is two (thus optimal) for any set of fault \(F\) (\(|F|\leq 2\)) and that the optimal routing can be computed in linear time. For the entire collection see [Zbl 0929.00074].