Planar Drawings of Plane Graphs

Shin-ichi NAKANO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E83-D    No.3    pp.384-391
Publication Date: 2000/03/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: INVITED SURVEY PAPER
Category: Graph Algorithms
Keyword: 
planar graph,  graph drawing,  algorithm,  graph theory,  

Full Text: PDF>>
Buy this Article


Summary: 
Given a plane graph G, we wish to find a drawing of G in the plane such that the vertices of G are represented as grid points, and the edges are represented as straight-line segments between their endpoints without any edge-intersection. Such drawings are called planar straight-line drawings of G. An additional objective is to minimize the area of the rectangular grid in which G is drawn. In this paper first we review known two methods to find such drawings, then explain a hidden relation between them, and finally survey related results.