Solution space investigation and comparison of modern data structures for heterogeneous 3D designs

Physical design algorithms are heavily impacted by the current trend towards 3D integration. This development requires new data structures specifically designed to take 3D-specific constraints into account. There has been rapid development in this field over the last several years. However, it is difficult to compare data structures and evaluate their applicability to new approaches. In this paper, we present a detailed overview of modern 3D data structures by investigating their solution spaces and their characteristics, such as redundancy and reachability. Layout designers and tool developers may find this information helpful as they assess new developments in this rapidly changing field.