There's a stronger theorem, due to Steiner I believe, saying that a triangulated planar graph can be realized as the 1-skeleton of a convex polyhedron. An appropriate projection of the convex polyhedron (so that one the image of one face contains all the others) gives a straight line embedding. It's easy to enhance a planar graph to make the complementary regions all be triangles. There's a still stronger theorem which Dan will recognize, since many years ago he worked on a computer implementation---the sphere cage theorem. Any polyhedral planar graph can be realized as the 1-skeleton of a convex polyhedron whose edges are tangent to the unit sphere. Such a realization is unique up to projective transformations of RP^3 that preserve the unit sphere. This follows from work of Koebe on combinatorial patterns of circle packings in the plane, also from work of Andreev on hyperbolic polyhedra, and is stuff I rediscovered and generalized. Bill Thurston On Wednesday, June 4, 2003, at 08:41 AM, Richard Guy wrote:
I believe that Tutte has a theorem that if a graph is planar, then it can be embedded using only straight line segments for edges. R.
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?
Most interesting to me is the case where the straight-line embedding is obtained via a continuous deformation, through embeddings, of the original one. (And I'm most interested in the case where each of the graph's finite complementary components is bounded by exactly 4 edges.)
--Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun