Oracle FAQ Your Portal to the Oracle Knowledge Grid
HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US
 

Home -> Community -> Usenet -> comp.databases.theory -> Re: dual graph (was: What databases have taught me)

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

From: Keith H Duggar <duggar_at_alum.mit.edu>
Date: 25 Jun 2006 18:22:59 -0700
Message-ID: <1151284979.344198.152780@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.

Received on Sun Jun 25 2006 - 20:22:59 CDT

Original text of this message

HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US