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 ≤ 3, in a graph G with n vertices. We denote with l the total length of the paths reported. For k ≤ 3, we present an optimal static data structure for G that uses O(n) space and executes k-path queries in output-sensitive O(l) time. We also give a semi-dynamic version of the data structure that supports a sequence of intermixed queries and insertions of vertices and edges in a planar graph, with worst-case query time O(l) and amortized insertion time O(log n). Our results make use of a new combinatorial structure for triconnected planar graphs that plays the same role as bipolar (st) orientations for biconnected planar graphs. This combinatorial structure also yields an alternative construction of convex drawings of triconnected planar graphs.
Research supported in part by the National Science Foundation under grant CCR-9423847, by the NATO Scientific Affairs Division under collaborative research grant 911016, by the Progetto Coordinato Ambienti di Supporto alla Progettazione di Sistemi Informativi of the Italian National Research Council, by the Progetto Bilaterale 94.23.CT07 Italia-USA of the Italian National Research Council, and by the Project Alcom-IT of the Esprit Program.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
G. Brightwell and W. T. Trotter. The order dimension of convex polytopes. SIAM J. Discrete Math., 6(2):230–245, 1993.
J. Cheriyan and S. N. Maheshwari. Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs. J. Algorithms, 9:507–537, 1988.
R. F. Cohen, G. Di Battista, A. Kanevsky, and R. Tamassia. Reinventing the wheel: an optimal data structure for connectivity queries. In Proc. 25th Annu. ACM Sympos. Theory Comput., pages 194–200, 1993.
H. de Fraysseix, P. O. de Mendez, and P. Rosenstiehl. Bipolar orientations revisited. Discrete Appl. Math., 56:157–179, 1995.
G. Di Battista and R. Tamassia. Incremental planarity testing. In Proc. 30th Annu. IEEE Sympos. Found. Comput. Sci., pages 436–441, 1989.
G. Di Battista and R. Tamassia. On-line graph algorithms with SPQR-trees. In Automata, Languages and Programming (Proc. ICALP '90), volume 442 of Lecture Notes in Computer Science, pages 598–611, 1990.
G. Di Battista and R. Tamassia. On-line maintenance of triconnected components with SPQR-trees. Algorithmica, to appear. Preprint: Technical Report CS-92-40, Comput. Sci. Dept., Brown Univ., 1992.
Y. Dinitz and A. Vainshtein. The connectivity carcass of a vertex subset in a graph and its incremental maintenance. In Proc. 26th Annu. ACM Sympos. Theory Comput., pages 716–725, 1994.
D. Eppstein, Z. Galil, G. F. Italiano, and A. Nissenzweig. Sparsification: A technique for speeding up dynamic graph algorithms. In Proc. 33rd Annu. IEEE Sympos. Found. Comput. Sci., pages 60–69, 1992.
D. Eppstein, Z. Galil, G. F. Italiano, and T. H. Spencer. Separator based sparsification for dynamic planar graph algorithms. In Proc. 25th Annu. ACM Sympos. Theory Comput., pages 208–217, 1993.
S. Even and R. E. Tarjan. Network flow and testing graph connectivity. SIAM J. Comput., 4:507–518, 1975.
S. Even and R. E. Tarjan. Computing an st-numbering. Theoret. Comput. Sci., 2:339–344, 1976.
A. Itai and M. Rodeh. The multi-tree approach to reliability in distributed networks. Inform. and Comput., 79(1):43–59, 1988.
A. Kanevsky, R. Tamassia, G. Di Battista, and J. Chen. On-line maintenance of the four-connected components of a graph. In Proc. Annu. IEEE Sympos. Found. Comput. Sci., pages 793–801, 1991.
G. Kant. Drawing planar graphs using the lmc-ordering. In Proc. 33rd Annu. IEEE Sympos. Found. Comput. Sci., pages 101–110, 1992.
J. A. La Poutré. Maintenance of triconnected components of graphs. In Automata, Languages and Programming (Proc. ICALP '92), volume 623 of Lecture Notes in Computer Science, 1992.
A. Lempel, S. Even, and I. Cederbaum. An algorithm for planarity testing of graphs. In Theory of Graphs: Internat. Symposium, pages 215–232, New York, 1967. Gordon and Breach.
H. Nagamochi and T. Ibaraki. A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica, 7:583–596, 1992.
M. Rauch. Improved data structures for fully dynamic biconnectivity. In Proc. 26th Annu. ACM Sympos. Theory Comput., pages 686–695, 1994.
W. Schnyder. Planar graphs and poset dimension. Order, 5:323–343, 1989.
W. Schnyder. Embedding planar graphs on the grid. In Proc. 1st ACM-SIAM Sympos. Discrete Algorithms, pages 132–148, 1990.
R. Tamassia. A dynamic data structure for planar graph embedding. In T. Lepisto and A. Salomaa, editors, Automata, Languages and Programming (Proc. ICALP '88), volume 317 of Lecture Notes in Computer Science, pages 576–590. Springer-Verlag, 1988.
D. Wagner and K. Weihe. A linear-time algorithm for edge-disjoint paths in planar graphs. In Algorithms (Proc. ESA '93), volume 726 of Lecture Notes in Computer Science, pages 384–395. Springer-Verlag, 1993.
J. Westbrook and R. E. Tarjan. Maintaining bridge-connected and biconnected components on-line. Algorithmica, 7:433–464, 1992.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Di Battista, G., Tamassia, R., Vismara, L. (1996). Output-sensitive reporting of disjoint paths (extended abstract). In: Cai, JY., Wong, C.K. (eds) Computing and Combinatorics. COCOON 1996. Lecture Notes in Computer Science, vol 1090. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61332-3_141
Download citation
DOI: https://doi.org/10.1007/3-540-61332-3_141
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61332-9
Online ISBN: 978-3-540-68461-9
eBook Packages: Springer Book Archive