Re: Linear embeddings of graphs


Dave Rusin wrote:
> At planarity.net there is a game in which we are presented with a
> finite planar graph and asked to find a piecewise linear embedding
> of it into R^2. It's fun for a while though one can find a method
> which seems to work for all graphs presented, and takes an amount
> of time proportional to the number of vertices. [...]

Such an algorithm has been published. The following information is from
http://mathworld.wolfram.com/PlanarStraightLineGraph.html :

] A graph embedding of a planar graph in which only straight line
] segments are used to connect the graph vertices. Fáry (1948)
] showed that every planar graph has an embedding which is a
] planar straight line graph with noncrossing edges (Bryant 1989;
] Skiena 1990, pp. 100 and 251; Scheinerman and Wilf 1994).
] de Fraysseix et al. (1988) give an algorithm for constructing a
] planar straight line for a graph of order n by placing the vertices
] on a (2n-4)x(n-2) grid (Skiena 1990, p. 251).

--- Christopher Heckman

P.S. The game was fun for me for about 5 seconds, and I quickly got
bored of it.

.

Relevant Pages