# Re: What databases have taught me

Date: 24 Jun 2006 14:39:13 -0700

Message-ID: <1151185153.172215.128580_at_m73g2000cwd.googlegroups.com>

Dmitry A. Kazakov wrote:

> On 24 Jun 2006 10:36:00 -0700, 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:
**> >
**> > http://mathworld.wolfram.com/DualGraph.html
**> >
**> > Can you explain it better?
**>
**> See:
**>
**> http://en.wikipedia.org/wiki/Planar_graph
**> http://en.wikipedia.org/wiki/Dual_graph
*

Neither of these provides an unambiguous specification of the problem.

> It is a quite intuitive thing. I was born in St.Petersburg, but you can

*> consider Venice for the same purpose. The graph of channels is the dual of
**> one of the bridges. Regions are the islands + one for mainland.
*

> > Is there some known theoretical complexity of this problem? (In other

*> > words, are you just setting me up? :-)
**>
**> It is not hard.
*

Reading about the history of the analysis of the problem, coupled with the fact that I can't seem to find a decent explanation of it, woud seem to contradict this. Perhaps it is only not hard after one has already learned about it.

> The problem specifically for RA lies elsewhere.

Ah, you do have something up your sleeve. How about you just come clean with it and we talk about it?

You know, the c.d.t. people are well aware of issue like transitive closure and Turing completeness, and how the traditional and various modern RAs stack up in comparison. We could discuss it if you wish.

Marshall Received on Sat Jun 24 2006 - 23:39:13 CEST