General circular permutation layout.

In the general circular permutation layout problem there are two concentric circles, C and C. There are a set of n inner terminals on C and a set of n outer terminals on C: terminals i on C and π on C are to be connected by means of a wire, where 1 ≤ i ≤ n. All wires must be realized in the interior of C. Each wire can intersect C at most once and at most K wires, for a fixed K, can pass between two adjacent inner terminals. A linear-time algorithm for obtaining a planar homotopy (single-layer realization) of an arbitrary instance of the general circular permutation layout problem, for K ≥ 0, is proposed. Previously, K = 1 has been studied. In this paper the algorithm is also extended to a more general problem, in which the number of wires allowed to pass between each pair of adjacent terminals on C may be different from pair to pair. [ABSTRACT FROM AUTHOR]