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

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