An algorithm for finding a forest in a planar graph-Case in which all terminals of each net lie on one of two specified face boundaries

Several routing problems such as VLSI river routing and one-layer routing can be formulated as a problem for finding a forest in a planar (grid) graph. Given a planar graph G together with nets of terminals, the present problem is to find a forest, i.e., a collection of vertex-disjoint trees, each of which interconnects all the terminals in a net. This paper gives a linear-time algorithm to solve the problem for the case all terminals of each net lie on one of two specified fact boundaries of G. [In Japanese.]