Jünger, Michael and Leipert, Sebastian
(1999)
Level Planar Embedding in Linear Time.
In: Graph Drawing 7th International Symposium, GD’99, September 1519, 1999
, pp. 7281(Official URL: http://dx.doi.org/10.1007/3540466487_7).
Full text not available from this repository.
Abstract
In a level directed acyclic graph G=(V,E) the vertex set V is partitioned into k \le V levels V^1, V^2,..., V^k such that for each edge (u,v) \in E with u \in V^i and v \in V^j we have i<j. 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,ki)  x \in R}, the edges are drawn monotonically with respect to the vertical direction, and no edges intersect expect 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 \le i \le 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 [6].
Available Versions of this Item

Level Planar Embedding in Linear Time. (deposited 23 Nov 2004)
[Currently Displayed]
Actions (login required)

View Item 