  The page-number of a directed acyclic graph (a DAG, for short) is the minimum
$k$ for which the DAG has a topological order and a $k$-coloring of its edges
such that no two edges of the same color cross, i.e., have alternating
endpoints along the topological order. In 1999, Heath and Pemmaraju conjectured
that the recognition of DAGs with page-number $2$ is NP-complete and proved
that recognizing DAGs with page-number $6$ is NP-complete [SIAM J. Computing,
1999]. Binucci et al. recently strengthened this result by proving that
recognizing DAGs with page-number $k$ is NP-complete, for every $k\geq 3$ [SoCG
2019]. In this paper, we finally resolve Heath and Pemmaraju's conjecture in
the affirmative. In particular, our NP-completeness result holds even for
$st$-planar graphs and planar posets.
