SINGLE-LAYER CHANNEL ROUTING AND PLACEMENT WITH SINGLE-SIDED NETS

This paper considers the optimal offset, feasible offset, and optimal placement problems for a more general form of single-layer VLSI channe l routing than has usually been considered in the past. Most prior wor ks require that every net has exactly one terminal on each side of the channel. As long as only one side of the channel contains multiple te rminals of the same net, we provide linear-time solutions to all three problems. Such results are implausible, if the placement of terminals is entirely unrestricted; in fact, the size of the output for the fea sible offset problem may be Omega(n(2)). The linear-time results also hold with a ragged boundary on the side of the channel with multiple c onnections to the same net.