Output-sensitive reporting of disjoint paths

A k-path query on a graph consists of computing k vertex-disjoint paths bet ween two given vertices of the graph, whenever they exist. In this paper we study the problem of performing k-path queries, with k less than or equal to 3, in a graph G with n vertices. We denote with l the total length of th e reported paths. For k less than or equal to 3, we present an optimal data structure for G that uses O(n) space and executes k-path queries in output -sensitive O(l) time. For triconnected planar graphs, our results make use of a new combinatorial structure that plays the same role as bipolar (st) o rientations for biconnected planar graphs. This combinatorial structure als o yields an alternative construction of convex grid drawings of triconnecte d planar graphs.