Treemaps for Directed Acyclic Graphs

Tsiaras, Vassilis and Triantafilou, Sofia and Tollis, Ioannis G. (2008) Treemaps for Directed Acyclic Graphs. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 377-388 (Official URL:

Full text not available from this repository.


Gene Ontology information related to the biological role of genes is organized in a hierarchical manner that can be represented by a directed acyclic graph (DAG). Treemaps graphically represent hierarchical information via a two-dimensional rectangular map. They efficiently display large trees in limited screen space. Treemaps have been used to visualize the Gene Ontology by first transforming the DAG into a tree. However this transformation has several undesirable effects such as producing trees with a large number of nodes and scattering the rectangles associated with the duplicates of a node around the screen. In this paper we introduce the problem of visualizing a DAG as a treemap, we present two special cases, and we discuss complexity results.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-77537-9_37
Classifications:P Styles > P.480 Layered
ID Code:853

Repository Staff Only: item control page


E. Baehrecke, N. Dang, K. Babaria, and B. Shneiderman,

"Visualization and analysis of microarray and gene ontology data with treemaps," BMC Bioinformatics, 5:84, (2004).

G. Di Battista, P. Eades, R. Tamassia and I.G.Tollis, Graph Drawing: Algorithms for the Visualization of graphs. Prentice - Hall, New Jersey, U.S.A., (1998).

B. Bederson, B. Shneiderman and M. Wattenberg, "Ordered and quantum treemaps: Making effective use of 2D space to display hierarchies," ACM Transactions on Graphics, V. 21, Is. 4, pp. 833, (2002).

S. Booth and S. Lueker, "Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms," Journal of Computer and System Sciences, V. 13, pp. 335, (1976).

M. Bruls, K. Huizing, and J. J. van Wijk, "Squarified treemaps," Proceedings of Joint Eurographics and IEEE TCVG Symposium on Visualization, Springer, pp. 33, (2000).

M. Garey and D. Johnson, "Complexity results for multiprocessor scheduling under resource constraints," SIAM Journal on Computing, V. 4, Is. 4, pp. 397, (1975).

D. Holten, "Hierarchical Edge Bundles: Visualization of Adjacency Relations in Hierarchical Data," IEEE Transactions on Visualization and Computer

Graphics, V. 12, No. 5, pp. 741, (2006).

W.-L. Hsu, "PC-Trees vs. PQ-Trees," Lecture Notes in Computer Science, V. 2108, pp. 207, (2001).

J. Meidanis, O. Port and G. Telles, "On the consecutive ones property," Discrete Applied Mathematics, V. 88, pp. 325, (1998).

Z. C. Shen and C. Chu, "Bounds on the Number of Slicing, Mosaic, and General Floorplans," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, V. 22, No. 10, pp. 1354, (2003).

B. Shneiderman, "Tree visualization with tree-maps: 2-d space-filling approach," ACM Transactions on Graphics, V. 11, Is. 1, pp. 92, (1992).

A. Symeonidis, I. Tollis and M. Reczko, "Visualization of Functional Aspects of microRNA Regulatory Networks Using the Gene Ontology," Lecture Notes in Computer Science, 4345, pp. 13-24, (2006).

J. Valdes, R. Tarjan, E.L. Lawler, "The recognition of Series Parallel digraphs," SIAM Journal on Computing, 11, pp. 289-313, (1982).