1
$\begingroup$

Is the crown graph the only type of directed acyclic graph whose partial order dimension could be potentially greater than 2 (given sufficiently many vertices in sets $U$ and $V$), given that for all edges, each points from a vertex in set $U$ to a vertex in set $V$?

Are there any DAGs (other than crowns) that have a partial order dimension greater than 2?

| cite | improve this question | | | | |
$\endgroup$
1
$\begingroup$

No, there are many other directed acyclic graphs with dimension greater than $2$.

By Schnyder's Theorem (1989), a graph is planar if and only if its incidence poset has dimension $\le 3$. The incidence poset is always a height $2$ directed acyclic graph. Therefore, all incidence posets of non-planar graphs have dimension $>3$.

Consider the non-planar graph $K_5$. It's incidence poset has $\binom{5}{2}$ maximal elements and $5$ minimal elements (so it's not a crown). By Schnyder, since $K_5$ is non-planar it's incidence poset must have dimension at least $4$.

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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