Keywords (2)

On Open Rectangle-of-Influence Drawings of Planar Graphs

On Open Rectangle-of-Influence Drawings of Planar Graphs,10.1007/978-3-642-02026-1_11,Huaming Zhangand,Milind Vaidya

On Open Rectangle-of-Influence Drawings of Planar Graphs   (Citations: 1)
BibTex | RIS | RefWorks Download
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 W + H £</font >{\cal W} + {\cal H} \leq (n-1), where W{\cal W} is the width of the grid, H{\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⌉ × ë</font >\lfloor(n-1)/2û</font >\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 11n/27\emph{11n/27} × 11n/27\emph{11n/27}. For quadrangulations, our asymptotical grid size bound 13n/27\emph{13n/27} × 13n/27\emph{13n/27} is the first known such bound.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: