Re: What databases have taught me

Marshall <marshall.spight_at_gmail.com> wrote:
> Dmitry A. Kazakov wrote:
> >
> > And, guys, what about presenting a query statement for building a dual
> > graph?
>
> I'm not at all familiar with graph theory. I couldn't make sense out of
> this:
>
> http://mathworld.wolfram.com/DualGraph.html
>
> Can you explain it better?
>
> Is there some known theoretical complexity of this problem? (In other
> words, are you just setting me up? :-)

Well, for one thing, a graph is planar if and only if it has a dual, and planarity testing is at least an intuitively complex problem. Bob Tarjan showed (in the 70's, I think) that is has a linear time solution using depth-first search trees. However, the algorithm is very nonobvious  and it was assumed for a long time than graph planarity testing could not be done in better than O(n^3) time. This implies that finding the dual of a graph is at least as hard, though I really doubt it's harder once you have found the layout of nodes that is planar, since you may then just find the geometric dual.

I don't know if that counts as "theoretical complexity", or precisely what you mean by that anyway.

HTH,

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