Visibility Drawings of Plane 3-Trees with Minimum Area |
| |
Authors: | Rahnuma Islam Nishat Debajyoti Mondal Md. Saidur Rahman |
| |
Affiliation: | 1. Graph Drawing and Information Visualization Laboratory, Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology (BUET), Dhaka, Bangladesh
|
| |
Abstract: | A visibility drawing of a plane graph G is a drawing of G where each vertex is drawn as a horizontal line segment and each edge is drawn as a vertical line segment such that the line segments use only grid points as their endpoints. The area of a visibility drawing is the area of the smallest rectangle on the grid which encloses the drawing. A minimum-area visibility drawing of a plane graph G is a visibility drawing of G where the area is the minimum among all possible visibility drawings of G. The area minimization for grid visibility representation of planar graphs is NP-hard. However, the problem can be solved for a fixed planar embedding of a hierarchically planar graph in quadratic time. In this paper, we give a polynomial-time algorithm to obtain minimum-area visibility drawings of plane 3-trees. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |