# Characterization of edge posets

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 , ) . 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.

• Isn't this the transitive closure of the DAG? en.wikipedia.org/wiki/Transitive_closure May 15 at 8:07
• @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.
– bof
May 15 at 8:14
• @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. May 15 at 8:17

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.