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