Oracle FAQ Your Portal to the Oracle Knowledge Grid
HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US
 

Home -> Community -> Usenet -> comp.databases.theory -> Re: What databases have taught me

Re: What databases have taught me

From: Chris Smith <cdsmith_at_twu.net>
Date: Sat, 24 Jun 2006 12:28:31 -0600
Message-ID: <MPG.1f07323629f15dd29896f5@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 Corporation
Received on Sat Jun 24 2006 - 13:28:31 CDT

Original text of this message

HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US