Another perhaps simpler way to derive a straight line drawing in every isotopy class of embeddings is to add extra edges until the graph is 3-connected, so the embedding is unique. On Thursday, June 5, 2003, at 08:25 PM, Erik Demaine wrote:

On Thu, 5 Jun 2003, Dan Asimov wrote:

...

But given that a graph G that can embedded in the plane can be embedded with all edges straight, however, doesn't immediately imply that the straight-line embedding *is* topologically equivalent to the original embedding (even though the graph itself is of course topologically the same).

If the graph is 3-connected, then the topological embedding is unique up to the choice of the outer face. Tutte's "How to Draw a Graph" allows you to specify the outer face in the straight-line drawing it produces. So for 3-connected graphs, you get exactly the topological embedding you want.

For graphs that are not 3-connected (like your square + a degree-2 vertex in the center), I assume you can decompose... E.g., suppose there is a vertex 2-cut {v,w}, and on one side you have G_1 and the other side you have G_2 (both of which contain v & w, and that is their only overlap). Let G'_1 be the graph & topological embedding obtained from G_1 with the edge {v,w} added where G_2 used to be. Ditto for G'_2. Then you can draw G'_1 and G'_2 by induction, and then nonuniformly scale G'_2's drawing down to be squished against the edge {v,w}, and then place it against the appropriate side of {v,w} in the drawing of G'_1.

Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun