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>
>
> 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/.
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