Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00181
On a Class of Planar Graphs with StraightLine Grid Drawings on Linear Area
Md. Rezaul Karim and
Md. Saidur Rahman
Vol. 13, no. 2, pp. 153177, 2009. Regular paper.
Abstract A straightline 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 straightline segment without edge crossings. It is well known that a planar graph of n vertices
admits a straightline grid drawing on a grid of area O(n^{2}). A lower bound of Ω(n^{2}) on the arearequirement for
straightline grid drawings of certain planar graphs are also known. In this paper, we introduce a fairly large class of planar graphs
which admits a straightline grid drawing on a grid of area O(n). We give a lineartime algorithm to find such a drawing.
Our new class of planar graphs, which we call "doughnut graphs,"
is a subclass of 5connected 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 straightline grid drawing with linear area.
But the recognition of a spanning subgraph of a "doughnut graph" seems to be a nontrivial problem, since the recognition of a
spanning subgraph
of a given graph is an NPcomplete problem in general.
We establish a necessary and sufficient condition for a 4connected
planar graph G to be a spanning subgraph of a "doughnut graph." We also give a lineartime algorithm to augment a 4connected
planar graph G to a "doughnut graph" if G satisfies the necessary and sufficient condition.

Submitted: April 2008.
Reviewed: January 2009.
Revised: February 2009.
Accepted: April 2009.
Final: April 2009.
Published: June 2009.
Communicated by
Petra Mutzel
