Geodesic
Universal Line-Sets for Drawing Planar 3-Trees
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Sixth International Workshop on Algorithms and Computation, WALCOM 2012 , Tome 17 (2013) no. 2, pp. 59-79.

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

A set S of lines is universal for drawing planar graphs with n vertices if every planar graph G with n vertices can be drawn on S such that each vertex of G is drawn as a point on a line of S and each edge is drawn as a straight-line segment without any edge crossing. It is known that ⎣[(2(n−1))/3]⎦ parallel lines are universal for any planar graph with n vertices. In this paper we show that a set of ⎣[(n+3)/2]⎦ parallel lines or a set of ⎡[(n+3)/4]⎤ concentric circles are universal for drawing planar 3-trees with n vertices. In both cases we give linear-time algorithms to find such drawings. A by-product of our algorithm is the generalization of the known bijection between plane 3-trees and rooted full ternary trees to the bijection between planar 3-trees and unrooted full ternary trees. We also identify some subclasses of planar 3-trees whose drawings are supported by fewer than ⎣[(n+3)/2]⎦ parallel lines. 
@article{JGAA_2013_17_2_a1,
     author = {Md. Iqbal Hossain and Debajyoti Mondal and Md. Saidur Rahman and Sammi Abida Salma},
     title = {Universal {Line-Sets} for {Drawing}  {Planar} {3-Trees}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {59--79},
     publisher = {mathdoc},
     volume = {17},
     number = {2},
     year = {2013},
     doi = {10.7155/jgaa.00285},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00285/}
}
TY  - JOUR
AU  - Md. Iqbal Hossain
AU  - Debajyoti Mondal
AU  - Md. Saidur Rahman
AU  - Sammi Abida Salma
TI  - Universal Line-Sets for Drawing  Planar 3-Trees
JO  - Journal of Graph Algorithms and Applications
PY  - 2013
SP  - 59
EP  - 79
VL  - 17
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00285/
DO  - 10.7155/jgaa.00285
LA  - en
ID  - JGAA_2013_17_2_a1
ER  - 
%0 Journal Article
%A Md. Iqbal Hossain
%A Debajyoti Mondal
%A Md. Saidur Rahman
%A Sammi Abida Salma
%T Universal Line-Sets for Drawing  Planar 3-Trees
%J Journal of Graph Algorithms and Applications
%D 2013
%P 59-79
%V 17
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00285/
%R 10.7155/jgaa.00285
%G en
%F JGAA_2013_17_2_a1
Md. Iqbal Hossain; Debajyoti Mondal; Md. Saidur Rahman; Sammi Abida Salma. Universal Line-Sets for Drawing  Planar 3-Trees. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Sixth International Workshop on Algorithms and Computation, WALCOM 2012
					, Tome 17 (2013) no. 2, pp. 59-79. doi : 10.7155/jgaa.00285. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00285/

Cité par Sources :