Paper Info
Title
Convex Grid Drwaings of Four-Connected Plane Graphs
Abstract
A convex grid drawing of a plane graph G is a drawing of G on the plane so that all vertices of G are put on grid points, all edges are drawn as straight-line segments between their endpoints without any edge-intersection, and every face boundary is a convex polygon. In this paper we give a linear-time algorithm for finding a convex grid drawing of any 4-connected plane graph G with four or more vertices on the outer face boundary. The algorithm yields a drawing in an integer grid such that W + H ≤ n - 1 if G has n vertices, where W is the width and H is the height of the grid. Thus the area W x H of the grid is at most ⌈(n-1)=2⌉ · ⌈(n-1)/2⌉. Our bounds on the grid sizes are optimal in the sense that there exist an infinite number of 4-connected plane graphs whose convex drawings need grids such that W + H = n-1 and W x H = ⌈(n - 1)/2⌉ · ⌈(n - 1)/2⌉.
Year
DOI
Venue
2000
10.1007/3-540-40996-3_22
International Symposium on Algorithms and Computation
Keywords
Field
DocType
n vertex,integer grid,convex grid drwaings,plane graph g,grid point,grid size,convex drawing,convex polygon,area w,convex grid drawing,four-connected plane graphs,4-connected plane graph,plane graph
Integer,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Convex polygon,Regular polygon,Connectivity,Mathematics,Planar graph,Grid
Conference
ISBN
Citations 
PageRank 
3-540-41255-7
11
0.84
References 
Authors
10
3
Name
Order
Citations
PageRank
Kazuyuki Miura1848.66
Takao Nishizeki21771267.08
Shin-ichi Nakano3265.62