Re: What databases have taught me

From: mAsterdam <>
Date: Sun, 25 Jun 2006 16:33:37 +0200
Message-ID: <449e9e64$0$31651$>

David Cressey wrote:
> Chris Smith wrote:

>>2. Identify all of the regions.  Regions are the empty spaces on your
>>paper, and are separated by edges from the graph.  The blank space
>>outside of where you've drawn the graph DOES count as a region, so there
>>is always at least one.  If the graph is a tree, for example, then there
>>is only one region, so the dual only has one vertex.

> Doesn't region identification depend on the topology of the space?

That complication is thrown out of scope by /planar/ in the problem-statement (which, I think, is accepted):

     Given A planar graph G, compute its dual graph G'

> If your graph were on the surface of a torus,
> wouldn't you come up with possibly different regions?
> (viz. the seven color map theorem for the surface of a
> torus)

"The person who says it cannot be done
should not interrupt the person doing it."
Chinese Proverb.
Received on Sun Jun 25 2006 - 16:33:37 CEST

Original text of this message