Re: What databases have taught me

From: Chris Smith <>
Date: Sat, 24 Jun 2006 12:28:31 -0600
Message-ID: <>

Marshall <> 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:
> 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 Corporation
Received on Sat Jun 24 2006 - 20:28:31 CEST

Original text of this message