Rectilinear Interconnections in the Presence of Obstacles
James P. Cohoon, Joseph L. Ganley · 2024
Often, a VLSI routing instance includes obstacles that the routing must not intersect, such as logic cells and wires in previously routed nets. This chapter examines techniques for optimal and near-optimal routing in the presence of obstacles. Much of the literature on two-terminal interconnections in the presence of obstacles is surveyed, and both new and previously published results on multi-terminal interconnections in the presence of obstacles are presented. Also, the problem of routing in the presence of obstacles is examined in the context of several interesting special cases. Both theoretical and practical considerations are addressed.