@inproceedings{a5f045aef3524460ace018a0f2d7d7e6,
title = "Rectangular grid drawings of plane graphs",
abstract = "The rectangular grid drawing of a plane graph G is a drawing of G such that each vertex is located on a grid point, each edge is drawn as a horizontal or vertical line segment, and the contour of each face is drawn as a rectangle. In this paper we give a simple linear-time algorithm to find a rectangular grid drawing of G if it exists. We also give an upper bound W+H ≤ n/2 on the sum of required width W and height H and a bound W+H ≤ n2/16 on the area of a rectangular grid drawing of G, where n is the number of vertices in G. These bounds are best possible, and hold for any compact rectangular grid drawing.",
author = "\{Saidur Rahman\}, Md and Nakano, \{Shin Ichi\} and Takao Nishizeki",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1996.; 2nd Annual International Conference on Computing and Combinatorics, COCOON 1996 ; Conference date: 17-06-1996 Through 19-06-1996",
year = "1996",
doi = "10.1007/3-540-61332-3\_142",
language = "English",
isbn = "9783540613329",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "92--105",
editor = "Jin-Yi Cai and Wong, \{Chak Kuen\} and Wong, \{Chak Kuen\}",
booktitle = "Computing and Combinatorics - 2nd Annual International Conference, COCOON 1996, Proceedings",
}