Algorithms for finding internally disjoint paths in a planar graph
Hitoshi Suzuki, Takehiro Akama, Takao Nishizeki · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 1989
Abstract Three efficient algorithms for finding vertex‐disjoint trees and internally disjoint paths in a planar graph are presented. Given a planar graph G and nets consisting of terminals lying on the external boundary, the first algorithm finds vertex‐disjoint trees, each of which interconnects all the terminals of a net. the second algorithm determines the maximum number k of internally disjoint paths between two specified vertices in the planar graph G. the third algorithm really finds these k paths. the time complexity of the first algorithm is O(n), those of the second and third are o(n log n). Here n is the number of vertices of the given graph G.