Re: What databases have taught me
Date: Sat, 24 Jun 2006 12:28:31 -0600
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
> 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.
-- Chris Smith - Lead Software Developer / Technical Trainer MindIQ CorporationReceived on Sat Jun 24 2006 - 20:28:31 CEST