Re: What databases have taught me
Date: Sun, 25 Jun 2006 16:33:37 +0200
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
-- "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