Given an acyclic directed graph $G$, the set $E(G)$ of edges of $G$ equipped with the reachable order $\to$ is called the edge poset of $G$, where for two edges $e_1\to e_2$ means that there is a directed path starting from $e_1$ ending with $e_2$.

My question is that how can we characterize those edge posets of acyclic directed graphs, or under exactly what conditions a poset can be represented as the edge poset of an acyclic directed graph?

A closely related result is stated in the paper "Planarity and Edge Poset Dimension", at page 733, where the authors said that:

*Posets which are edge partial orders of graphs have been fully characterized (see , for example , [13]) . They are called N-free partial orders as they do not contain any N-shaped configuration . They are also characterized by the property that any maximal chain intersects any maximal antichain . We have the following property :

PROPERTY 3 . Each N - free partial order is the edge - partial order of an unique e - bipolarly oriented graph.*

This result means that the edge poset of an e-bipolarly oriented graph (or equivalently, an st-graph /PERT-graph) can be characterized by the property of N-freeness.

But I do not agree with the statement that posets which are edge partial orders of graphs have been fully characterized, which is what my question concerns.

  • $\begingroup$ Isn't this the transitive closure of the DAG? en.wikipedia.org/wiki/Transitive_closure $\endgroup$ May 15 at 8:07
  • $\begingroup$ @MatthieuLatapy No. The elements of the "edge poset" are the edges, not the vertices. For instance, the $4$-element poset whose Hasse diagram looks like the letter N can not be represented as an edge poset. $\endgroup$
    – bof
    May 15 at 8:14
  • $\begingroup$ @Matthieu Latapy Yes, the reachable order of vertices is exactly the transitive closure of the adjacency relation of a DGA. But my question is about the reachable order of edges, not of vertices. $\endgroup$
    – xuexing lu
    May 15 at 8:17

1 Answer 1


The result that each N - free partial order is the edge - partial order of an unique e - bipolarly oriented graph, implies that a poset is an edge poset if and only if it is N-free.

Proof:$(\Rightarrow)$ We prove that edge posets are N-free by contradiction. Suppose $P$ is the edge-poset of acyclic directed graph $G$ and is not N-free, then it contains a covering-subposet $N$ with four elements $\{a,b,c,d\}$ such that $a$ covers $b$, $c$ covers $b$, $c$ covers $d$, $a||c$, $a||d$ and $b||d$. Evidently, the edges conrresponding to $a,b,c,d$ and their incident vertices form a sub acyclic directed graph of $G$ (an edge-induced subgraph), whose edge-poset is $N$. This contradicts with the fact that $N$ can not be an edge-poset.

$(\Leftarrow)$ This direction is a direct consequence of the fact that any N-free poset is the edge poset of an unique PERT-graph.

The conrrespondence between N-free posets and acyclic directed graphs are one-to-many. In fact, we can freely combine and split the sources and sinks of an acyclic directed graph, respectively, without changing its edge-poset. It is natural to introduce the following notion.

Two acyclic directed graphs are EP-equivalent if they have the same edge-poset.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.