Grid Drawings of 4-Connected Plane Graphs |
| |
Authors: | K Miura S Nakano T Nishizeki |
| |
Institution: | (1) Graduate School of Information Sciences, Tohoku University, Aoba-yama 05, Sendai 980-8579, Japan \{miura, nishi\}@nishizeki.ecei.tohoku.ac.jp , JP;(2) Department of Computer Science, Faculty of Engineering, Gunma University, 1-5-1 Tenjin-cho, Kiryu, Gunma 376-8515, Japan nakano@cs.gunma-u.ac.jp, JP |
| |
Abstract: | A grid drawing of a plane graph G is a drawing of G on the plane so that all vertices of G are put on plane grid points and all edges are drawn as straight line segments between their endpoints without any edge-intersection.
In this paper we give a very simple algorithm to find a grid drawing of any given 4-connected plane graph G with four or more vertices on the outer face. The algorithm takes time O(n) and yields a drawing in a rectangular grid of width \lceil n/2 \rceil - 1 and height \lfloor n/2\rfloor if G has n vertices. The algorithm is best possible in the sense that there are an infinite number of 4-connected plane graphs, any
grid drawings of which need rectangular grids of width \lceil n/2 \rceil - 1 and height \lfloor n/2\rfloor .
Received October 13, 1999, and in revised form July 18, 2000. Online publication February 26, 2001. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|