Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00164
Convex Grid Drawings of Plane Graphs with Rectangular Contours
Vol. 12, no. 2, pp. 197-224, 2008. Regular paper.
Abstract In a convex drawing of a plane graph,
all edges are drawn as straight-line segments without any edge-intersection and
all facial cycles are drawn as convex polygons.
In a convex grid drawing,
all vertices are put on grid points.
A plane graph G has a convex drawing
if and only if G is internally triconnected,
and an internally triconnected plane graph G has a convex grid drawing on an (n−1) ×(n−1) grid
if either G is triconnected or
the triconnected component decomposition tree T(G) of G has two or three leaves,
where n is the number of vertices in G.
In this paper, we show that
an internally triconnected plane graph G has a convex grid drawing
on a 2n ×n2 grid if T(G) has exactly four leaves.
We also present an algorithm to find such a drawing in linear time.
Our convex grid drawing has a rectangular contour,
while most of the known algorithms
produce grid drawings having triangular contours.
|
Submitted: August 2007.
Reviewed: June 2008.
Revised: July 2008.
Accepted: July 2008.
Final: July 2008.
Published: October 2008.
Communicated by
Xin He
|
Journal Supporters
|