A Canadian is traveling on an outerplanar graph...

The Canadian Traveler tries to go from a vertex to another in a given weighted graph. But some edges are blocked; this will be discovered when visiting one of their endpoints. The traveler’s strategy can be evaluated by the ratio between the traveled distance and the optimal distance that would have been traveled had the information on blocked edges been perfect; this is called the competitive ratio, which we seek to minimize. It is well-known that no strategy can have competitive ratio better than \(2k+1\) (where \(k\) is the number of blocked edges), even in unweighted planar graphs of treewidth 2.

We study the case of outerplanar graphs, where we construct a strategy with competitive ratio 9 in the unweighted case (which implies bounded ratio when the gap between weights is bounded). We also show that this value of 9 is a lower bound: there is a family on which no strategy can achieve competitive ratio 9-epsilon. Finally, we show that the competitive ratio is unbounded in arbitrarily weighted outerplanar graphs.