Oracle FAQ | Your Portal to the Oracle Knowledge Grid |
Home -> Community -> Usenet -> comp.databases.theory -> Re: What databases have taught me
Bob Badour wrote:
> David Cressey wrote:
> > Doesn't region identification depend on the topology of the space? If you
> > 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)
>
> If it were on a torus, it would not be on a plane.
mAsterdam wrote:
> 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'
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/. 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.