Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(2)
Planar Graph
Plane Graph
Subscribe
Academic
Publications
On Open RectangleofInfluence Drawings of Planar Graphs
On Open RectangleofInfluence Drawings of Planar Graphs,10.1007/9783642020261_11,Huaming Zhangand,Milind Vaidya
Edit
On Open RectangleofInfluence Drawings of Planar Graphs
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Huaming Zhangand
,
Milind Vaidya
We investigate open rectangleofinfluence drawings for irreducible triangulations, which are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. An open rectangleofinfluence drawing of a
plane graph
G is a type of straightline grid drawing where there is no vertices drawn in the proper inside of the axisparallel 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 (n1), 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 ⌈(n1)/2⌉ × ë</font >\lfloor(n1)/2û</font >\rfloor [8]. In this paper, we prove that the two straightline grid drawing algorithms for irreducible triangulations from [4] and quadrangulations from [3,5] actually produce open rectangleofinfluence drawings for them respectively. Therefore, the straightline grid drawing size bounds from [3,4,5] also hold for the open rectangleofinfluence 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.
Conference:
Conference on Combinatorial Optimization and Applications  COCOA
, pp. 123134, 2009
DOI:
10.1007/9783642020261_11
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.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
dx.doi.org
)
(
www.informatik.unitrier.de
)
More »
References
(8)
Convex Drawings of 3Connected Plane Graphs
(
Citations: 20
)
Nicolas Bonichon
,
Stefan Felsner
,
Mohamed Mosbah
Conference:
Symposium on Graph Drawing  GD
, pp. 6070, 2004
Drawing planar graphs nicely
(
Citations: 40
)
N. Chiba
,
K. Onoguchi
,
T. Nishizeki
Journal:
Acta Informatica  ACTA
, 1985
On Finding the Rectangular Duals of Planar Triangular Graphs
(
Citations: 45
)
Xin He
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 22, no. 6, pp. 12181226, 1993
Regular Edge Labeling of 4Connected Plane Graphs and Its Applications in Graph Drawing Problems
(
Citations: 89
)
Goos Kant
,
Xin He
Journal:
Theoretical Computer Science  TCS
, vol. 172, no. 12, pp. 175193, 1997
Planar graphs and poset dimension
(
Citations: 107
)
Walter Schnyder
Journal:
A Journal on The Theory of Ordered Sets and Its Applications  Order
, vol. 5, no. 4, pp. 323343, 1989
Sort by:
Citations
(1)
Closed RectangleofInfluence Drawings for Irreducible Triangulations
Sadish Sadasivam
,
Huaming Zhang
Journal:
Computational Geometry: Theory and Applications  COMGEO
, vol. 44, no. 1, pp. 409418, 2010