Grid Drawings of Four-Connected Plane Graphs

概要

論文の詳細を見る
Given a plane graph G, we wish to draw it in the plane, according to the given embedding, in such a way that the vertices of G are drawn as grid points, and the edges are drawn as straight-line segments between their endpoints. It is known that if a 4-connected plane graph G has at least four vertices on its exterior face, then G can be drawn in a W×H grid such that W+H≤n, W≤(n+3)/2and H≤2(n-1)/3[He95]. In this paper we show that this type of graphs can be drawn in a ⌊(n -1)/2j⌋×⌈(n -1)/2⌉ grid.
社団法人電子情報通信学会の論文
1996-03-11