| > anyone have a favorite planar graph layout alrogithm that they could
> share? something along the lines of:
>
> given graph g of vertices v and edges e, layout the
> vertices in a plane such that the crossing number of the
> resultant graph is 0, and the edges are represebted as
> straight lines.
>
> by planar graph, i really mean a planar straight line graph (pslg).
> the non straight line case is much less interesting.
> -paul
Let's standardize some notation. Trying not to get bogged down in
futile formality...
PLANE GRAPH: A drawing of points and lines in the Euclidean plane, with no
two lines crossing, etc.
S.L. PLANE GRAPH: Ditto, but all the lines are straight
PLANAR GRAPH: Abstract graph which can be drawn as a plane graph
S.L. PLANAR GRAPH: Abstract graph which can be drawn as an S.L. plane graph
Theorem 1: Every planar graph is S.L. planar.
This is obviously equivalent to the following:
Theorem 1': Every edge-maximal planar graph is S.L. planar.
By edge-maximal planar I mean that (1) the graph is planar (2) if I
add any edge to it then it is no longer planar. The following intermediate
results suggest themselves immediately...
Lemma 1: a plane graph representation of an edge-maximal planar graph will
satisfy the following property:
sum(i=1...n) (d_i-6) = -12
where d_i is the number of edges hanging off vertex i.
Proof: Either you know it already or it's a fun exercise
Lemma 2: Let G be an edge-maximal planar graph, of order n > 3. Let
v, v' & v" be mutually adjacent vertices of G. We say that F = {v, v', v"}
is a *face* if F is *not* a cutset of G. Then G has exactly 2n - 4 faces.
Sketch of Proof: In any plane graph representing G, the space will be divided
up into 2n - 4 regions, each bounded by 3 mutually adjacent points. These
three points cannot be a cutset (careful), therefore correspond to a face.
But any face in G must be appear as one of these regions. Thus there are
exactly 2n - 4 faces.
To return to the main theorem. As is sometimes the case with
inductive proofs, it is easier to prove a stronger statement.
Theorem 1": Every edge-maximal planar graph is flexibly S.L. planar.
where I define:
FLEXIBLY S.L. PLANAR GRAPH: Abstract graph which, given any identified face, F,
can be drawn as an s.l. plane graph in which the region of the plane
corresponding to F is the region of infinite area, the 'outside' of the
graph.
So, now let's prove Theorem 1".
Proof: Induction on number of vertices. Obviously for up to four vertices,
there is no problem. Suppose we know that the result holds for all
edge-maximal planar graphs with < n vertices (n>4). Let G be an edge-maximal
planar graph with n vertices. Pick some face, F, from the 2n-4 possibilities.
Since n > 3, no vertex has degree < 3. Therefore, by Lemma 1, there
are at least 4 vertices of degree =< 5. Since F contains 3 vertices, we
can say that there is at least one vertex not of F with degree =< 5. Call
one such vertex v.
Remove v, and all the edges hanging off it, and we are left
with a graph, H', with N-1 vertices. Now, the trick is that we need to add
some edges to H' to make it edge-maximal again. G was edge-maximal, and you
need only look at a plane graph, P, of G to see that the only possibly newly
permissible edges are those running *between* two vertices adjacent to v in G.
Now, we have a CASE statement on the degree of v in G.
degree 3: add no edges. already edge-maximal. The three vertices form
one *T-triangle* T1.
degree 4: add one edge. This is possible else v and its neighbours formed
a K5 in P (five mutually adjacent vertices), which is *not* possible.
The four vertices form two T-triangles, T1 & T2.
degree 5: add two edges, connecting one neighbour of v to two others. Again,
this must be possible. The five vertices form three T-triangles, T1,T2,T3.
This gives us an edge-maximal planar graph H, with one less vertex than
G, three less edges, and two less faces. Moreover, F still exists as a face
of H. By the induction hypothesis, H is flexibly s.l. planar, and let Q be an
s.l. plane graph drawing of it, with F as the outside region. Now, in Q, the
thing to focus on are the pictures of the (one, two or three) T-triangles, Tj.
Firstly, each of them has finite area. Ie: none of them is the
'outside' region of the picture, since F has that role, and we have defined
ourselves to be keeping well clear of F.
Secondly, each of them is nevertheless a face, and thus contains no
internal vertices. Thus each T-triangle in Q is just that: an ordinary
convex straight-sided triangle.
Now, if v had degree 3, we can insert a vertex into T-1, in H
and connect it to each corner with a straight-line segment. Since a
triangle is convex, this works for any internal point we care to choose.
This gives us an s.l. plane graph of G.
If v had degree 4, then T-1 and T-2 share an edge (the one which was
temporarily added). Remove this edge, and place a vertex somewhere along
its length, connecting it by straight line segments to the four corners.
Since a triangle is convex, and we have chosen a point on the intersection of
two triangles, this works for any internal point on the joining lines. This
gives us an s.l. plane graph of G.
If v had degree 5, then (wlog) T-1 and T-2 share an edge, and so
do T-2 and T-3. Remove these two edges (which are the ones which were
added temporarily). Now the point where the two edges join is clearly a
point common to all three triangles. But that is already occupied by
another point! However, any point 'reasonably close' to this point will
'work'. (Need to tighten up the argument here). Anyway, we then link
the new point to each of the five neighbours of v, and we have an
s.l. plane graph of G.
So G is flexibly s.l. planar. Q.E.D., Pat on back, etc.
*******************
Now, how far does this take us in building an algorithm? A long
way in fact. Most of the complexities of the proof result from the
special treatment accorded to F (a consequence of the fact that we're doing
this stuff on the plane rather than on the more natural medium for this
theorem which is the sphere). But in the algorithm, you just pick F at the
beginning, and that is going to be the outside triangle of the drawing, with
all the other points coming inside.
However, there are two design issues that need to be addressed when
dealing with the algorithm:
(1) Selecting where to draw the next point. At each stage, we are adding
a new point within a triangle, quadrilateral or pentagon. We don't want the
points to be too close to one another. A small amount of linear programming
will determine for each shape what the open set of valid positions is. This
is trivial for the triangle, but needs more work for the others, especially
the pentagon.
Moreover, we want to take account of the fact that some faces that we build
will have to contain other points at later stages, and should be built
bigger to permit this. It seems that some weighting algorithm, to
determine which of the newly-built faces should have what relative size,
should be used to get a nice-looking graph.
(2) The theorem as presented works for edge-maximal graphs. What happens
for graphs which are not edge-maximal? Do we have to first add lots of
edges to the graph?
The main reason for working with edge-maximal graphs is to reduce the
number of qualitatively different situations which the system has to handle.
If not, then I must sometimes draw a point and decide arbitrarily *which*
region that point must lie in. If I make the wrong choice then later in the
algorithm, I may find that I have to back track to this choice point. With
the edge-maximal approach, I never have to make such choices. The face into
which a new point must go is always determined, although I do have choice
as to fine-tuning within that region, for aesthetic purposes.
For instance, suppose that my graph on 6 vertices contains the edges:
AB,BC,AC
AD,BD
AE,BE
DF,CF
Say I draw ABC as the outside face. Then I may draw D within ABC, connected
to A & B. But when it comes to drawing E, does it go in ABD or ADBC?
It must be the former, because F will need to connect to both C and D.
But how do I *know* this, when I am drawing the point?
If I have added the edges BF, AF and DE, so that the graph is edge-maximal,
then the difficulty does not arise.
However, computing an edge-maximal version of the graph in a pre-processor
seems overkill. I want something I can do on-the-fly. Having 'solved' the
problem, it is frustrating to discover this stubborn issue. Any ideas
anyone?
|