In this thesis we consider the global routing problem, which arises as one of the major subproblems in the physical design step in VLSI design. In global routing, we are given a three-dimensional grid graph G with edge ...

Axis-aligned rectangle packings can be characterized by the set of spatial relations that hold for pairs of rectangles (west, south, east, north). A representation of a packing consists of one satisfied spatial relation ...