Geodesic
On a Class of Planar Graphs with Straight-Line Grid Drawings on Linear Area
Journal of Graph Algorithms and Applications, Tome 13 (2009) no. 2, pp. 153-177.

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. It is well known that a planar graph of n vertices admits a straight-line grid drawing on a grid of area O(n2). A lower bound of Ω(n2) on the area-requirement for straight-line grid drawings of certain planar graphs are also known. In this paper, we introduce a fairly large class of planar graphs which admits a straight-line grid drawing on a grid of area O(n). We give a linear-time algorithm to find such a drawing. Our new class of planar graphs, which we call "doughnut graphs," is a subclass of 5-connected planar graphs. We show several interesting properties of "doughnut graphs" in this paper. One can easily observe that any spanning subgraph of a "doughnut graph" also admits a straight-line grid drawing with linear area. But the recognition of a spanning subgraph of a "doughnut graph" seems to be a non-trivial problem, since the recognition of a spanning subgraph of a given graph is an NP-complete problem in general. We establish a necessary and sufficient condition for a 4-connected planar graph G to be a spanning subgraph of a "doughnut graph." We also give a linear-time algorithm to augment a 4-connected planar graph G to a "doughnut graph" if G satisfies the necessary and sufficient condition.
DOI : 10.7155/jgaa.00181
Keywords: graph drawing, straight-line drawing, doughnut graph, grid drawing, planar graph, linear area drawing 
@article{JGAA_2009_13_2_a4,
     author = {Md. Rezaul Karim and Md. Saidur Rahman},
     title = {On a {Class} of {Planar} {Graphs} with {Straight-Line} {Grid} {Drawings} on {Linear} {Area}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {153--177},
     publisher = {mathdoc},
     volume = {13},
     number = {2},
     year = {2009},
     doi = {10.7155/jgaa.00181},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00181/}
}
TY  - JOUR
AU  - Md. Rezaul Karim
AU  - Md. Saidur Rahman
TI  - On a Class of Planar Graphs with Straight-Line Grid Drawings on Linear Area
JO  - Journal of Graph Algorithms and Applications
PY  - 2009
SP  - 153
EP  - 177
VL  - 13
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00181/
DO  - 10.7155/jgaa.00181
LA  - en
ID  - JGAA_2009_13_2_a4
ER  - 
%0 Journal Article
%A Md. Rezaul Karim
%A Md. Saidur Rahman
%T On a Class of Planar Graphs with Straight-Line Grid Drawings on Linear Area
%J Journal of Graph Algorithms and Applications
%D 2009
%P 153-177
%V 13
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00181/
%R 10.7155/jgaa.00181
%G en
%F JGAA_2009_13_2_a4
Md. Rezaul Karim; Md. Saidur Rahman. On a Class of Planar Graphs with Straight-Line Grid Drawings on Linear Area. Journal of Graph Algorithms and Applications, Tome 13 (2009) no. 2, pp. 153-177. doi : 10.7155/jgaa.00181. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00181/

Cité par Sources :