dual graph (was: What databases have taught me)

From: mAsterdam <mAsterdam_at_vrijdag.org>
Date: Mon, 26 Jun 2006 00:28:25 +0200
Message-ID: <449f0dab$0$31637$e4fe514c_at_news.xs4all.nl>


Keith H Duggar wrote:
> mAsterdam wrote:

>>David Cressey wrote:
[snip]

>>>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'

>
> It's clear that Chris Smith was talking about an embedding
> in the plane. That said, graph planarity is independent of
> whether the graph is or is not embedded. Saying that a graph
> is planar is simply a statement that an embedding in the
> plane (without crossings) is possible. However, a planar
> graph can be embedded in other spaces and yet it is still a
> planar /graph/.

Yes, (after re-reading I can't see how I missed it) it appears you and David are right, the complication of the topology of the space is still in scope. Before I make a fool of myself again:
could you restate the problem in such a way that it /is/ out?

> Consider, what would you call a graph with
> no subgraphs homeomorphic to K5 or K3,3 when embedded on a
> torus? It would still be called a planar graph I believe.

?

-- 
"The person who says it cannot be done
should not interrupt the person doing it."
Chinese Proverb.
Received on Mon Jun 26 2006 - 00:28:25 CEST

Original text of this message