# Re: dual graph

Date: Mon, 26 Jun 2006 13:33:51 -0600

Message-ID: <MPG.1f09e46d415818989712_at_news.altopia.net>

Dmitry A. Kazakov <mailbox_at_dmitry-kazakov.de> wrote:

> G is ordered if DAG.

Eh? That's not a grammatically correct sentence, and I can't figure out what you mean by it. If it was supposed to mean "G is ordered if G is a DAG", then that's not true. Here are some possible true statements involving ordered graphs and DAGs. Did you mean one or more of these?

- A DAG (like any other graph) can be given an order.
- If an order is assigned to a DAG such that for all directed edges (P, Q), P <= Q, then the order is called a topological order, and topological orders have certain interesting properties on DAGs.
- Given an order for an arbitrary (undirected) graph, the graph can be oriented in such a way that the order is the topological order of the resulting DAG.

(Incidentally, it's not true that a DAG has a unique topological order. There can be any number of orderings that are topological. That's probably worth mentioning, since it is something your sentence above may have have been supposed to mean.)

In fact, though, the possibility of ordering is not really related to DAGs at all. All graphs, whether they are directed or not, have cycles or not, are planar or not, *whatever*, may ge given an order. In fact, they may be given p! different possible orders, where p is the number of nodes.

> Its transitive closure G* is a strict order [on

*> nodes].
*

No. The transitive closure of a directed acyclic graph does define an order on the set of nodes. An order on the graph itself, though, has nothing to do with the edges of that graph (though, of course, it could be expressed as a /different/ graph... but that's not really very relevant, is it?)

*>
*

> [ 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*.
*

-- Chris Smith - Lead Software Developer / Technical Trainer MindIQ CorporationReceived on Mon Jun 26 2006 - 21:33:51 CEST