Optimal Labeling for Connectivity Checking in Planar Networks with Obstacles
Bruno Courcelle, Cyril Gavoille, Mamadou Moustapha Kanté, Andrew Twigg · 2009
We consider the problem of determining in a planar graph G whether two vertices x and y are linked by a path that avoids a set X of vertices and a set F of edges. We attach labels to vertices in such a way that this fact can be determined from the labels of x and y, the vertices in X and the ends of the edges of F. For a planar graph with n vertices, we construct labels of size O(log n). The problem is motivated by the need to quickly compute alternative routes in networks under node or edge failures.