ISSN:
1432-0541
Keywords:
Key words. Connectivity, Triconnected graph, Biconnected graph, Disjoint paths, Coloring, Graph drawing.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00009264
Permalink