DAGmaps and ε-Visibility Representations of DAGs

Tollis, Ioannis G. and Tsiaras, Vassilis (2010) DAGmaps and ε-Visibility Representations of DAGs. In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009, Chicago, IL, USA , pp. 357-368 (Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_34).

Full text not available from this repository.

Abstract

DAGmaps are space filling visualizations of DAGs that generalize treemaps. Deciding whether or not a DAG admits a DAGmap is NP-complete. Recently we defined a special case called one-dimensional DAGmap where the admissibility is decided in linear time. However there is no complete characterization of the class of DAGs that admit a onedimensional 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 give a characterization of the DAGs that admit directed ε-visibility representations. Finally we show that a DAGmap defines a directed three-dimensional ε-visibility representation of a DAG. Keywords: DAGmap, Treemap, DAG, Visibility.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-11805-0_34
Classifications:P Styles > P.900 Visibility
P Styles > P.999 Others
ID Code:1110

Repository Staff Only: item control page

References

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

Bose, P., Everett, H., Fekete, S.P., Houle, M.E., Lubiw, A., Meijer, H., Romanik, K., Rote, G., Shermer, T.C., Whitesides, S., Zelle, C.: A visibility representation for graphs in three dimensions. Journal of Graph Algorithms and Applications 2, 1–16 (1998)

Bruls, M., Huizing, K., van Wijk, J.: Squarified treemaps. In: de Leeuw, W., van Liere, R. (eds.) Data Visualization 2000, Proceedings of the Second Joint Eurographics and IEEE TCVG Symposium on Visualization, pp. 33–42 (2000)

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, Upper Saddle River (1998)

Di Battista, G., Tamassia, R.: Algorithms for plane representations of acyclic digraphs. Theoretical Computer Science 61(2-3), 175–198 (1988)

Di Battista, G., Tamassia, R.: On-line maintenance of triconnected components with SPQR-trees. Algorithmica 15(4), 302–318 (1996)

Kant, G., Liotta, G., Tamassia, R., Tollis, I.G.: A visibility representation for graphs in three dimensions. Area requirement of visibility representations of trees 62, 81–88 (1997)

Lü, H., Fogarty, J.: Cascaded treemaps: examining the visibility and stability of structure in treemaps. In: ACM Proceedings of graphics interface 2008, pp. 259–266 (2008)

Romanik, K.: Directed VR-representable graphs have unbounded dimension. In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 177–181. Springer, Heidelberg (1995)

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

Tamassia, R., Tollis, I.G.: A unified approach to visibility representations of planar graphs. Discrete and Computational Geometry 1(1), 321–341 (1986)

Tsiaras, V.: Algorithms for the Analysis and Visualization of Biomedical Networks. Ph.D. thesis, Computer Science Department, University of Crete (2009) (submitted)

Tsiaras, V., Triantafilou, S., Tollis, I.G.: DAGmaps: Space Filling Visualization of Directed Acyclic Graphs. Journal of Graph Algorithms and Applications 13(3), 319–347 (2009)

Valdes, J., Tarjan, R.E., Lawler, E.L.: The recognition of series parallel digraphs. SIAM Journal on Computing 11(2), 298–313 (1982)

Wismath, S.K.: Characterizing bar line-of-sight graphs. In: SCG 1985: Proceedings of the first annual symposium on Computational geometry, pp. 147–152. ACM, New York (1985)