Geodesic
Radial Level Planarity Testing and Embedding in Linear Time
Journal of graph algorithms and applications, Special Issue on Selected Papers from the Eleventh International Symposium on Graph Drawing, GD 2003 , Tome 9 (2005) no. 1, pp. 53-97 Cet article a éte moissonné depuis la source Journal of Graph Algorythms and Applications website

Voir la notice de l'article

A graph with an ordered k-partition of the vertices is radial level planar if there is a strictly outward drawing on k concentric levels without crossings. Radial level planarity extends level planarity, where the vertices are placed on k horizontal lines and the edges are routed strictly downwards without crossings. The extension is characterised by rings, which are certain level non-planar biconnected components. Our main results are linear time algorithms for radial level planarity testing and for computing a radial level planar embedding. We introduce PQR-trees as a new data structure where R-nodes and associated templates for their manipulation are introduced to deal with rings. Our algorithms extend level planarity testing and embedding algorithms, which use PQ-trees. 
@article{JGAA_2005_9_1_a4,
     author = {Christian Bachmaier and Franz Brandenburg and Michael Forster},
     title = {Radial {Level} {Planarity} {Testing} and {Embedding} in {Linear} {Time}},
     journal = {Journal of graph algorithms and applications},
     pages = {53--97},
     year = {2005},
     volume = {9},
     number = {1},
     doi = {10.7155/jgaa.00100},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00100/}
}
TY  - JOUR
AU  - Christian Bachmaier
AU  - Franz Brandenburg
AU  - Michael Forster
TI  - Radial Level Planarity Testing and Embedding in Linear Time
JO  - Journal of graph algorithms and applications
PY  - 2005
SP  - 53
EP  - 97
VL  - 9
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00100/
DO  - 10.7155/jgaa.00100
LA  - en
ID  - JGAA_2005_9_1_a4
ER  - 
%0 Journal Article
%A Christian Bachmaier
%A Franz Brandenburg
%A Michael Forster
%T Radial Level Planarity Testing and Embedding in Linear Time
%J Journal of graph algorithms and applications
%D 2005
%P 53-97
%V 9
%N 1
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00100/
%R 10.7155/jgaa.00100
%G en
%F JGAA_2005_9_1_a4
Christian Bachmaier; Franz Brandenburg; Michael Forster. Radial Level Planarity Testing and Embedding in Linear Time. Journal of graph algorithms and applications, 
							Special Issue on Selected Papers from the Eleventh International Symposium on Graph Drawing, GD 2003
					, Tome 9 (2005) no. 1, pp. 53-97. doi: 10.7155/jgaa.00100

Cité par Sources :