Box-Rectangular Drawings of Plane Graphs |
| |
| Authors: | Md Saidur Rahman Shin-ichi Nakano Takao Nishizeki |
| |
| Institution: | Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology, Dhaka, 1000, Bangladeshf1;Department of Computer Science, Gunma University, Kiryu, 376-8515, Japan, f2;Graduate School of Information Sciences, Tohoku University, Aoba-yama 05, Sendai, 980-8579, Japan, f3 |
| |
| Abstract: | In this paper we introduce a new drawing style of a plane graph G called a box-rectangular drawing. It is defined to be a drawing of G on an integer grid such that every vertex is drawn as a rectangle, called a box, each edge is drawn as either a horizontal line segment or a vertical line segment, and the contour of each face is drawn as a rectangle. We establish a necessary and sufficient condition for the existence of a box-rectangular drawing of G. We also give a linear-time algorithm to find a box-rectangular drawing of G if it exists. |
| |
| Keywords: | graph algorithm graph drawing rectangular drawing box-drawing box-rectangular drawing |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
