# Re: dual graph (was: What databases have taught me)

Date: 25 Jun 2006 18:22:59 -0700

Message-ID: <1151284979.344198.152780_at_m73g2000cwd.googlegroups.com>

mAsterdam wrote:

> 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?
*

Graph theory is definitely /not/ something I have a deep understanding of. I think Chris was just trying to help give Marshall a more intuitive feel for the problem. Hence the description of a graph embedded in a plane etc. I was just pointing out that a graph is or is not planar regardless of what space you embed it in.

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

A graph is planar if and only if it contains no subgraphs "equivalent" (for a particular notion of equivalence in this case homeomorphism) to either K5 or K3,3. K5 is the graph of 5 completely connected nodes. In other words an edge from each node to every other node. And K3,3 is a graph with two groups of three nodes where each node is connected to every node in the other group.

So you see the planarity of a graph can be stated without any reliance on embedding.

- Keith -- Fraud 6