Linear embeddings of graphs


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.

My question has to do with the "nicest" possible embedding of the
graphs given. When you play the game on "level N", the graph you
are given evidently contains (N+2)(N+3)/2 vertices and N(N+2) edges,
and the degrees of the vertices are all 2, 3, or 4. The graphs
I have seen are all connected, and they are stated to be all planar.
Not all the graphs presented on level N are isomorphic, and indeed it
may be true that the program is randomly selecting from the set of all
planar graphs which meet the conditions I have just mentioned.
It's not clear how the authors of the program are creating these
graphs and are certain that they are planar; if I had to do it,
I would randomly draw edges to connect points that are already IN
the plane, choosing only edges that don't intersect edges already drawn.

Since the numbers of vertices are always triangular numbers, I thought
perhaps the program authors did just this, starting with a dense set of
vertices packed in the triangular lattice (i.e. the complex points which
lie in the ring Z[w] where w is a cube root of unity). Indeed,
the unique isomorphism type of graph for level 1 can be drawn by
adding 8 line segments to the six points in a small triangle, and
each of the two graphs I have seen for level 2 can be drawn in this way.

At level 3 there are at least 5 non-isomorphic graphs that meet the
conditions I have stated. (They can be proved non-isomorphic e.g. by
considering the subgraphs of their degree-4 vertices.) I don't think
they can all be formed by drawing 24 non-intersecting line segments
between points in the triangle of 15 points. What is a good way to
prove this?

My most convinving argument uses the fact that the perimeter of the
triangle is made of 12 graph edges (maybe more, since there is no
a priori reason to exclude a graph which happens not to contain
all the edges which make up the boundary of the convex hull of the points).
On the other hand, when I do find a linear embedding of the graphs
in the game, they typically have a smaller perimeter. But this
argument is weak -- there is more than one possible PL embedding of
these graphs, so while there does seem to be a "natural" boundary,
more or less, in most of the cases, I don't know how to find all
possible boundaries.

There are other constraints as well since it seems clear, in practice,
that there are few candidates for the vertices which can be mapped to
the three corners of the triangle. Only in very constrained circumstances
can those vertices have degree 4, for example. On the other hand,
whenever three vertices on the "boundary" of the graph are mutually
connected, at least one of them would have to map to a corner of the
triangle.

So as a practical matter it's pretty easy to convince myself that
any given graph has no PL planar embedding into the complete graph
on the vertices of the regular triangle. But are there some invariants
one may use to give a rigorous proof of this fact?

I would also be interested to know what algorithm really is used to
generate these graphs.

FWIW the scoring system is pretty unfair: there is an "expected" time
of 100N seconds to complete level N (you get a bonus of one point for
each second by which you beat this time), even though it seems obvious
that the amount of time needed to complete the task will have to be O(N^2)
no matter what algorithm is used to play the game.

I have only worked through the first 17 or so levels, so maybe there are
additional twists which are only become evident at higher levels of play.

dave
.