Re: dual graph

From: Dmitry A. Kazakov <>
Date: Mon, 26 Jun 2006 20:09:30 +0200
Message-ID: <xnhqm4tazibp$.m1c6iamjjjl0$>

On Mon, 26 Jun 2006 08:55:02 -0600, Chris Smith wrote:

> David Cressey <> wrote:

>> 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?
> Well, such a graph has no cycles, so it is a forest.  If it's connected, 
> then it's a tree.  I don't know where Dmitry got "ordered".

G is ordered if DAG. Its transitive closure G* is a strict order [on nodes].

[ OK, planarity is lost, but it is not required for hierarchies either. ]

> Any graph 
> (planar or not, cycles or not, doesn't matter) may be made into an 
> ordered graph simply by defining an order for its nodes.

If you can order the set of nodes. But that order is not necessary G*.

Dmitry A. Kazakov
Received on Mon Jun 26 2006 - 20:09:30 CEST

Original text of this message