Parallel Algorithms for Trapezoid Graphs and Asteroidal-Triple Free Graphs
Presentation
Overview
Overview
Description
In two-sided channel routing on a VLSI chip it is often convenient to represent signal nets by trapezoids. In this representation the four corners of the trapezoids are the right-most and left-most terminals on the upper side and lower side of the channel respectively.
The maximum set of non-intersecting trapezoids is of particular interest since corresponding signal nets can be safely assigned to the same layer in the channel routing. Similarly, a Steiner set is of interest to determine best way of connecting different nets.
