Level planar embedding in linear time

A level graph G =(V,E,φ) is a directed acyclic graph with a mapping φ: V →{1, 2,...,k}, k ≥ 1, that partitions the vertex set V as V = V 1 ∪V 2 ∪···∪V k, V j = φ −1 (j), V i ∩V j = ∅ for i � = j, such that φ(v) ≥ φ(u) + 1 for each edge (u, v) ∈ 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∈V i are drawn on the line li = {(x, k − i) | x ∈ Ê}, 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 ≤ i ≤ k). We present an O(|V|) time algorithm for embedding level planar graphs. This approach is based on a level planarity test by Jünger, Leipert, and Mutzel (1998)