4 Jun
2003
4 Jun
'03
6:27 a.m.
On Wed, 4 Jun 2003 asimovd@aol.com wrote:
Suppose a finite graph G is embedded in the plane topologically. When can it be embedded so that all the edges are straight lines?
Fary's Theorem (exercise 6.2.6 in Intro to Graph Theory 2nd ed, by Douglas West) says that every simple planar graph has a straight-line embedding. West also says that Schnyder in 1992 proved that if the planar graph has n vertices then there is a straight-line embedding in which the vertices are located at integer points in the grid [1,n-1]x[1,n-1]. --Edwin