Geodesic
DAGmaps and ε-Visibility Representations for DAGs: Algorithms and Characterizations
Journal of Graph Algorithms and Applications, Tome 16 (2012) no. 2, pp. 359-380.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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 
@article{JGAA_2012_16_2_a9,
     author = {Vassilis Tsiaras and Ioannis Tollis},
     title = {DAGmaps and {\ensuremath{\varepsilon}-Visibility} {Representations} for {DAGs:} {Algorithms} and {Characterizations}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {359--380},
     publisher = {mathdoc},
     volume = {16},
     number = {2},
     year = {2012},
     doi = {10.7155/jgaa.00262},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00262/}
}
TY  - JOUR
AU  - Vassilis Tsiaras
AU  - Ioannis Tollis
TI  - DAGmaps and ε-Visibility Representations for DAGs: Algorithms and Characterizations
JO  - Journal of Graph Algorithms and Applications
PY  - 2012
SP  - 359
EP  - 380
VL  - 16
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00262/
DO  - 10.7155/jgaa.00262
LA  - en
ID  - JGAA_2012_16_2_a9
ER  - 
%0 Journal Article
%A Vassilis Tsiaras
%A Ioannis Tollis
%T DAGmaps and ε-Visibility Representations for DAGs: Algorithms and Characterizations
%J Journal of Graph Algorithms and Applications
%D 2012
%P 359-380
%V 16
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00262/
%R 10.7155/jgaa.00262
%G en
%F JGAA_2012_16_2_a9
Vassilis Tsiaras; Ioannis Tollis. DAGmaps and ε-Visibility Representations for DAGs: Algorithms and Characterizations. Journal of Graph Algorithms and Applications, Tome 16 (2012) no. 2, pp. 359-380. doi : 10.7155/jgaa.00262. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00262/

Cité par Sources :