Re: dual graph

From: Dmitry A. Kazakov <mailbox_at_dmitry-kazakov.de>
Date: Mon, 26 Jun 2006 20:09:30 +0200
Message-ID: <xnhqm4tazibp$.m1c6iamjjjl0$.dlg@40tude.net>

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

> David Cressey <dcressey_at_verizon.net> 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*.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Received on Mon Jun 26 2006 - 13:09:30 CDT