# Re: What databases have taught me

Date: Sat, 24 Jun 2006 12:28:31 -0600

Message-ID: <MPG.1f07323629f15dd29896f5_at_news.altopia.net>

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