Geodesic
Straight-Line Grid Drawings of Label-Constrained Outerplanar Graphs with O(n log n) Area
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Third Annual Workshop on Algorithms and Computation (WALCOM 2009) , Tome 15 (2011) no. 3, pp. 437-456.

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

A straight-line grid drawing of a planar graph G is a drawing of G on an integer grid such that each vertex is drawn as a grid point and each edge is drawn as a straight-line segment without edge crossings. Any outerplanar graph of n vertices with maximum degree d has a straight-line grid drawing with area O(dnlogn). In this paper, we introduce a subclass of outerplanar graphs, which we call label-constrained outerplanar graphs, that admits straight-line grid drawings with O(nlogn) area. We give a linear-time algorithm to find such a drawing. We also give a linear-time algorithm for the recognition of label-constrained outerplanar graphs. 
@article{JGAA_2011_15_3_a5,
     author = {Md. Rezaul Karim and Md. Jawaherul Alam and Md. Saidur Rahman},
     title = {Straight-Line {Grid} {Drawings} of {Label-Constrained} {Outerplanar} {Graphs} with {O(n} log n) {Area}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {437--456},
     publisher = {mathdoc},
     volume = {15},
     number = {3},
     year = {2011},
     doi = {10.7155/jgaa.00233},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00233/}
}
TY  - JOUR
AU  - Md. Rezaul Karim
AU  - Md. Jawaherul Alam
AU  - Md. Saidur Rahman
TI  - Straight-Line Grid Drawings of Label-Constrained Outerplanar Graphs with O(n log n) Area
JO  - Journal of Graph Algorithms and Applications
PY  - 2011
SP  - 437
EP  - 456
VL  - 15
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00233/
DO  - 10.7155/jgaa.00233
LA  - en
ID  - JGAA_2011_15_3_a5
ER  - 
%0 Journal Article
%A Md. Rezaul Karim
%A Md. Jawaherul Alam
%A Md. Saidur Rahman
%T Straight-Line Grid Drawings of Label-Constrained Outerplanar Graphs with O(n log n) Area
%J Journal of Graph Algorithms and Applications
%D 2011
%P 437-456
%V 15
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00233/
%R 10.7155/jgaa.00233
%G en
%F JGAA_2011_15_3_a5
Md. Rezaul Karim; Md. Jawaherul Alam; Md. Saidur Rahman. Straight-Line Grid Drawings of Label-Constrained Outerplanar Graphs with O(n log n) Area. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Third Annual Workshop on Algorithms and Computation (WALCOM 2009)
					, Tome 15 (2011) no. 3, pp. 437-456. doi : 10.7155/jgaa.00233. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00233/

Cité par Sources :