DAGmaps: Space Filling Visualization of Directed Acyclic Graphs

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). Space filling visualizations, such as the treemaps, have the capacity to display thousands of items legibly in limited space via a two-dimensional rectangular map. 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 display rectangle. In this paper we introduce the problem of visualizing a DAG with space filling techniques without converting it to a tree first, we present two special cases of the problem, and we discuss complexity issues. Submitted: January 2008 Reviewed: April 2008 Revised: August 2008 Accepted: December 2008 Final: January 2009 Published: November 2009 Article type: Regular paper Communicated by: S.-H. Hong and T. Nishizeki This work was supported in part by INFOBIOMED code: IST-2002-507585 and the Greek General Secretariat for Research and Technology under Program “ARISTEIA”, Code 1308/B1/3.3.1/317/12.04.2002. E-mail addresses: tsiaras@ics.forth.gr (Vassilis Tsiaras) striant@ics.forth.gr (Sofia Triantafilou) tollis@ics.forth.gr (Ioannis G. Tollis) 320 Tsiaras, Triantafilou, Tollis DAGmaps