Re: What databases have taught me

From: Chris Smith <cdsmith_at_twu.net>
Date: Sat, 24 Jun 2006 22:00:15 -0600
Message-ID: <MPG.1f07b8374b49cf619896f9_at_news.altopia.net>


Marshall <marshall.spight_at_gmail.com> wrote:
> First I need to know what a "graph" is. (Don't laugh.)
>
> I think of the term as meaing "nodes and edges" but it
> appears for this paticular problem, we need faces as
> well. Yes/no? What are these faces? Are they collections
> of edges? Do the nodes have a position? If so, what
> must be the position of the nodes in the dual? If
> it's not specified, then how can we say the dual of
> the dual of the graph is the graph? Apparently it's okay
> to leave some things out, but it's not clear what.
>
> Then I need to know what "dual" is. Etc.

In case this helps, if you are planning to try this.

And you're done. As a simple example, take this graph:

    O ----------- O

    |           / |
    |   A     /   |
    |       /     |
    |     /       |    C
    |   /    B    |
    | /           |

    O ----------- O

There are three regions (two inside, and then the "outside" region) which I've labelled A, B, and C. The dual therefore has three vertices. There are two edges that separate A from C (the top and left edges), so there are two edges from A to C in the dual. Following the same pattern, the dual has two edges from B to C, and one edge from A to B. The dual is:

                  A
                 /|\
                | | |
                 \| |
                  C |
                 /| |
                | | |
                 \|/
                  B

  • Here is a definite possible subtlety. All graphs have duals, but all duals are not graphs. In fact, the dual constructed above is not a graph. Rather, it is a multigraph. More generally, we also need to allow loops as well, so a dual is a pseudo-graph.

Even more generally (though you can probably ignore this detail) duals are relationships between planar embeddings of graphs -- which means ways to draw the graph in the plane without crossing edges. So, if you did step 1 differently above, you might get a different dual. In practice, it is normal to say something like "a graph may have more than one dual", when it would probably be more correct to say "each planar embedding of a graph has one and only one dual, which is itself a planar embedding of a graph."

  • Yes, there is always some way of finding the dual of a dual of a graph that can get you back to the original graph. However, since a graph has multiple duals, there may be other paths that don't do so. (Technically, the unique dual of the unique dual of a planar embedding of a graph does bring you reliably back to the original, but assuming you don't plan to store information about the planar embedding, that's not really relevant.)

Finally, I'm not convinced that merely guaranteeing that the graph is planar is sufficient to find the dual of a graph. What you need is some specific planar embedding of the graph. Otherwise, you'll need to calculate a planar embedding for step #1, and that's just as hard as proving that the graph is planar... i.e., knowing in advance that it's planar doesn't actually get you anywhere. I actually don't know offhand  what a common way is to describe a planar embedding. Obviously you could ask for a list of the regions, which would make your job somewhat easier.

-- 
Chris Smith - Lead Software Developer / Technical Trainer
MindIQ Corporation
Received on Sun Jun 25 2006 - 06:00:15 CEST

Original text of this message