Oracle FAQ | Your Portal to the Oracle Knowledge Grid |
Home -> Community -> Usenet -> comp.databases.theory -> Re: What databases have taught me
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 | | / |
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
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."
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 CorporationReceived on Sat Jun 24 2006 - 23:00:15 CDT