On Open Rectangle-of-Influence Drawings of Planar Graphs

We investigate open rectangle-of-influence drawings for irreducible triangulations, which are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. An open rectangle-of-influence drawing of a plane graph

G

is a type of straight-line grid drawing where there is no vertices drawn in the proper inside of the axis-parallel rectangle defined by the two end vertices of any edge. The algorithm presented by Miura and Nishizeki [8] uses a grid of size

${\cal W} + {\cal H} \leq$

(n-1)

, where

${\cal W}$

is the width of the grid,

${\cal H}$

is the height of the grid and

n

is the number of vertices in

G

. Thus the area of the grid is at most ⌈(n-1)/2⌉ ×

$\lfloor$

(n-1)/2

$\rfloor$

[8].

In this paper, we prove that the two straight-line grid drawing algorithms for irreducible triangulations from [4] and quadrangulations from [3,5] actually produce open rectangle-of-influence drawings for them respectively. Therefore, the straight-line grid drawing size bounds from [3,4,5] also hold for the open rectangle-of-influence drawings. For irreducible triangulations, the new asymptotical grid size bound is

$\emph{11n/27}$

×

$\emph{11n/27}$

. For quadrangulations, our asymptotical grid size bound

$\emph{13n/27}$

×

$\emph{13n/27}$

is the first known such bound.