Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00262 DAGmaps and ε-Visibility Representations for DAGs: Algorithms and Characterizations Vassilis Tsiaras and Ioannis G. Tollis Vol. 16, no. 2, pp. 359-380, 2012. Regular paper Abstract DAGmaps are space filling visualizations of DAGs that generalize treemaps. Deciding whether or not a DAG admits a DAGmap is NP-complete. Although any layered planar DAG admits a one-dimensional DAGmap there was no complete characterization of the class of DAGs that admit a one-dimensional DAGmap. In this paper we prove that a DAG admits a one-dimensional DAGmap if and only if it admits a directed ε-visibility representation. Then we characterize the class of DAGs that admit directed ε-visibility representations. This class consists of the DAGs that admit a downward planar straight-line drawing such that all source and sink vertices are assigned to the external face. Finally we show that a DAGmap defines a directed three-dimensional ε-visibility representation of a DAG. Key words: Graph Drawing, Visibility Representations, DAGmaps, Treemaps, Planar st-Graphs
|
Final: May 2012. Revised: April 2012. Published: May 2012. Submitted: November 2011. Reviewed: February 2012. Accepted: April 2012. Communicated by Antonios Symvonis |
Journal of Graph Algorithms and Applications |