Re: What databases have taught me

Marshall <marshall.spight_at_gmail.com> wrote:
> > - You don't need faces; just a (unordered) nodes and edges.
>
> Are you sure?
>
> Consider a square, with four points, top-left, top-right, bottom-left,
> bottom-right. Now add a fifth edge, from top-right to bottom-left.
>
> If this edge goes through the interior of the square, that is a
> different set of regions than if it goes around the outside of
> the square.

Yes, those are different planar embeddings, so they have different duals. (The duals happen to be isomorphic to each other in this case, but that's just a coincidence; not necessarily guaranteed to always be true.) This gets back to the fact that duals are really an operation on planar embeddings[*] of graphs rather than on graphs. The phrase "dual of a graph" means "a dual of some planar embedding of that graph". So using either embedding would give you a correct answer. However, yes you would need to pick an embedding of the graph at some point to use the geometric algorithm. (The combinatorial dual, which is equivalent to a geometric dual but is defined in a completely different way, may be more amenable to computation via the relational model than a planar embedding of the graph. However, you'll have to find someone who knows about it to explain combinatorial duals to you.)

I didn't think of that as needing faces... mainly because the word "faces" was used in a different sense by the MathWorld article that someone posted a link to earlier (it was talking about the threedimensional  analog of a dual for a polyhedral graph), and I just assumed that you saw the word "faces" there.

[*] Since someone brought up topology, I suppose this would be an opportune time to point out that duals are formally described in terms of embeddings on a sphere, rather than a plane. That turns out to be equivalent, because the embedding can't possibly depend on every single point of the sphere, so it's always possible to remove a point of the sphere and thus turn it into the topological equivalent of a plane. The use of a sphere turns out to be different from use of a plane, except that it removes that messiness about having to specify that "outside" counts as a region. I am not familiar with embeddings on torii (sp?) and thus can't comment on that aspect of the conversation. It certainly seems reasonable that there could be graphs that could be embedded on torii but which are not planar, in which case there may be something like a torus-embedding that's analogous to a dual; but if so, that is not what is normally meant by the word "dual".

-- 
Chris Smith - Lead Software Developer / Technical Trainer
MindIQ Corporation