Hierarchical data visualization using a fast rectangle-packing algorithm

This paper presents a technique for the representation of large-scale hierarchical data which aims to provide good overviews of complete structures and the content of the data in one display space. The technique represents the data by using nested rectangles. It first packs icons or thumbnails of the lowest-level data and then generates rectangular borders that enclose the packed data. It repeats the process of generating rectangles that enclose the lower-level rectangles until the highest-level rectangles are packed. This paper presents two rectangle-packing algorithms for placing items of hierarchical data onto display spaces. The algorithms refer to Delaunay triangular meshes connecting the centers of rectangles to find gaps where rectangles can be placed. The first algorithm places rectangles where they do not overlap each other and where the extension of the layout area is minimal. The second algorithm places rectangles by referring to templates describing the ideal positions for nodes of input data. It places rectangles where they do not overlap each other and where the combination of the layout area and the distances between the positions described in the template and the actual positions is minimal. It can smoothly represent time-varying data by referring to templates that describe previous layout results. It is also suitable for semantics-based or design-based data layout by generating templates according to the semantics or design.