Re: dual graph

From: David Cressey <dcressey_at_verizon.net>
Date: Mon, 26 Jun 2006 11:34:59 GMT
Message-ID: <DDPng.9169$U%1.4899_at_trndny07>


"Keith H Duggar" <duggar_at_alum.mit.edu> wrote in message news: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
>

Thanks to everybody for clearing up the matter of "planar".

Now, I'm interested in a a subset of the planar graphs.

It's the graphs that don't divide the space into more than one region.

It seems to me that it's appropriate to call such graphs "hierarchical graphs", or simply "hierarchies". But I'm not sure. Can anyone clear this up?

(And please skip over the comment that you can call it anything you want. We all know that.) Received on Mon Jun 26 2006 - 13:34:59 CEST

Original text of this message