Jünger, Michael and Leipert, Sebastian (1999) Level Planar Embedding in Linear Time. [Conference Paper]
 | There is a more recent version of this eprint available. Click here to view it. |
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,k-i) | 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].
| Item Type: | Conference Paper |
|---|---|
| Classifications: | M Methods > M.500 Layered G Algorithms and Complexity > G.490 Embeddings P Styles > P.480 Layered |
| ID Code: | 273 |
| Deposited By: | Maciejak, Agnes |
| Deposited On: | 23 Nov 2004 |
| Last Modified: | 18 Sep 2008 13:08 |
| Alternative Locations: | http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=1731&spage=72 |
Available Versions of this Item
- Level Planar Embedding in Linear Time. (deposited 23 Nov 2004) [Currently Displayed]
Repository Staff Only: item control page
