ISSN:
1432-0541
Keywords:
Noncrossing paths
;
Shortest path
;
Plane graphs
;
Single-layer routing
;
VLSI
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01955681