Re: What databases have taught me
From: mAsterdam <mAsterdam_at_vrijdag.org>
Date: Sun, 25 Jun 2006 16:33:37 +0200
Message-ID: <449e9e64$0$31651$e4fe514c_at_news.xs4all.nl>
>
>
> Doesn't region identification depend on the topology of the space?
Date: Sun, 25 Jun 2006 16:33:37 +0200
Message-ID: <449e9e64$0$31651$e4fe514c_at_news.xs4all.nl>
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