# Re: What databases have taught me

Date: 25 Jun 2006 14:17:43 -0700

Message-ID: <1151270263.649546.199680_at_u72g2000cwu.googlegroups.com>

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.

- Keith -- Fraud 6