Summary: A level graph \(G= (V,E,\phi)\) is a directed acyclic graph with a mapping \(\phi: V\to \{1,2,\dots, k\}\), \(k\geq 1\), that partitions the vertex set \(V\) as \(V= V^1\cup V^2\cup\cdots\cup V^k\), \(V^j= \phi^{-1}(j)\), \(V^i\cap V^j= \emptyset\) for \(i\neq j\), such that \(\phi(v)\geq \phi(u)+ 1\) for each edge \((u,v)\in E\). The level planarity testing problem is to decide if \(G\) can be drawn in the plane such that for each level \(V^i\), all \(v\in V^i\) are drawn on the line \(l_i= \{(x,k- i)\mid x\in\mathbb{R}\}\), the edges are drawn monotonically with respect to the vertical direction, and no edges intersect except at their end vertices.
In order to draw a level planar graph without edge crossings, a level planar embedding of the level graph has to be computed. Level planar embeddings are characterized by linear orderings of the vertices in each \(V^i\) \((1\leq i\leq k)\). We present an \(O(|V|)\) time algorithm for embedding level planar graphs. This approach is based on a level planarity test by M. Jünger, S. Leipert and P. Mutzel [Lect. Notes Comput. Sci. 1547, 224-237 (1998)].