Re: dual graph

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?

1. A DAG (like any other graph) can be given an order.
2. 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.
3. 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. ]

You've really lost me now. The question was what to call a graph whose dual has only one node (i.e., the edges don't divide the plane). The correct answer is "forest" (or "tree", if we assume connectedness). "Ordered" is decidedly not a correct answer.

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

Of course I can order the set of nodes. I just start somewhere, and start counting, like so... 1, 2, 3, 4, and so on. Who cares if the order I come up with is equivalent to the transitive closure of a directed graph?

-- 
Chris Smith - Lead Software Developer / Technical Trainer
MindIQ Corporation