Abstract
Let G be an undirected plane graph with nonnegative edge length, and letk terminal pairs lie on two specified face boundaries. This paper presents an algorithm for findingk “noncrossing paths” inG, each connecting a terminal pair, and whose total length is minimum. Noncrossing paths may share common vertices or edges but do not cross each other in the plane. The algorithm runs in timeO(n logn) wheren is the number of vertices inG andk is an arbitrary integer.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974.
W. Dai, T. Asano, and E. S. Kuh, Routing region definition and ordering scheme for building-block layout,IEEE Trans. Computer-Aided Design,4(3) (1985), 189–197.
G. N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications,SIAM J. Comput.,16 (1987), 1004–1022.
H. N. Gabow and R. E. Tarjan, A linear-time algorithm for a special case of disjoint set union,J. Comput. System Sci.,30 (1985), 209–221.
J. JáJá,An Introduction to Parallel Algorithms, Addison Wesley, Reading, MA, 1992.
P. N. Klein, A linear processor polylog-time algorithm for shortest path in planar graphs,Proc. 34th Symp. on Foundations of Computer Science, pp. 259–270, 1993.
M. R. Kramer and J. van Leewen, Wire-routing is NP-complete, Report No. RUU-CS-82-4, Department of Computer Science, University of Utrecht, Utrecht, 1982.
D. T. Lee, C. F. Shen, C. D. Yang, and C. K. Wong, Non-crossing path problems, Manuscript, Dept. of EECS, Northwestern University, 1991.
J. F. Lynch, The equivalence of theorem proving and the interconnection problem,ACM SIGDA Newsletter,5(3) (1975), 31–36.
H. Suzuki, T. Akama, and T. Nishizeki, Algorithms for finding internally-disjoint paths in a planar graph,Trans. IECE,J71-A(10) (1988), 1906–1916 (in Japanese).
H. Suzuki, T. Akama, and T. Nishizeki, Finding Steiner forests in planar graphs,Proc. First SIAM-ACM Symp. on Discrete Algorithms, pp. 444–453, 1990.
R. E. Tarjan,Data Structures and Network Algorithms, SIAM, Philadelphia, PA, 1983.
J. Takahashi, H. Suzuki, and T. Nishizeki, Algorithms for finding noncrossing paths with minimum total length in plane graphs,Proc. ISAAC '92, Lecture Notes in Computer Science, vol. 650, Springer-Verlag, Berlin, pp. 400–409, 1992.
Author information
Authors and Affiliations
Additional information
Communicated by K. Melhorn.
Rights and permissions
About this article
Cite this article
Takahashi, J., Suzuki, H. & Nishizeki, T. Shortest noncrossing paths in plane graphs. Algorithmica 16, 339–357 (1996). https://doi.org/10.1007/BF01955681
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01955681