The paper is concerned with solutions to permutation layout problems such that i) no wire passes the upper area of the upper horizontal line, and ii) no wire intersects the lower horizontal line more than once. A necessary and sufficient condition for a problem to have such a solution is given. The set of all the solutions to the given problem is characterized in a graph theoretical way. A linear time algorithm is also given.

In this paper is given a necessary and sufficient condition for a permutation layout problem to have a wiring pattern such that no wire passes the upper area of the upper horizontal line, no wire intersects the lower horizontal line more than once, and between-pins congestion is not more than k, where the portion of the lower horizontal line which is placed to the left (resp., right) of the leftmost (resp., rightmost) terminal is considered to be a between-pins spacing. A linear time algorithm is given for the case k1, based on a graph theoretical representation of the condition.