Re: [math-fun] Geometry/topology question about planar graphs
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
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
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
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
participants (4)
-
asimovd＠aol.com -
Edwin Clark -
Richard Guy -
William Thurston