Abstract.
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 \leq 3 \) , in a graph G with n vertices. We denote with \( \ell \) the total length of the reported paths. For \( k \leq 3 \) , we present an optimal data structure for G that uses O(n) space and executes k -path queries in output-sensitive \( O(\ell) \) 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received August 24, 1996; revised April 8, 1997.
Rights and permissions
About this article
Cite this article
Di Battista, G., Tamassia, R. & Vismara, L. Output-Sensitive Reporting of Disjoint Paths . Algorithmica 23, 302–340 (1999). https://doi.org/10.1007/PL00009264
Issue Date:
DOI: https://doi.org/10.1007/PL00009264