Name
Abstract | ||
|---|---|---|
A convex grid drawing of a plane graph G is a drawing of G on the plane such that all vertices of G are put on grid points, all edges are drawn as straight-line segments 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 every 4-connected plane graph G with four or more vertices on the outer face. The size of the drawing satisfies W + H <= n - 1, where n is the number of vertices of G, W is the width and H is the height of the grid drawing. Thus the area W center dot H is at most [(n - 1)/2] - [(n - 1)/2]. Our bounds on the sizes are optimal in a sense that there exist an infinite number of 4-connected plane graphs whose convex drawings need grids such that W + H = n - I and W center dot H = [(n - 1)/2] - [(n - 1)/2]. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1142/S012905410600425X | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE |
Keywords | Field | DocType |
plane graph | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Convex polygon,Regular polygon,Dominance drawing,Planar graph,Mathematics,Grid | Journal |
Volume | Issue | ISSN |
17 | 5 | 0129-0541 |
Citations | PageRank | References |
8 | 0.68 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kazuyuki Miura | 1 | 84 | 8.66 |
| Shin-ichi Nakano | 2 | 246 | 24.40 |
| Takao Nishizeki | 3 | 1771 | 267.08 |