Jünger, Michael and Leipert, Sebastian (1999) Level Planar Embedding in linear Time. [Preprint]
 | There is a more recent version of this eprint available. Click here to view it. |
Full text available as:
![[img]](http://gdea.informatik.uni-koeln.de/style/images/fileicons/application_pdf.png) | PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader 345Kb |
Abstract
A level graph G = (V,E,lev) is a directed acyclic graph with a mapping lev : V -> {1,2,dots,k}, k >= 1, that partitions the vertex set V as V = V1 u V2 u...u Vk, Vj = lev^{-1}(j), Vi n Vj = 0 for i != j, such that lev(v) >= lev(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 Vi, all v in Vi 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 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 Vi (1 <= i <= k). We present an order(|V|) time algorithm for embedding level planar graphs. This approach is based on a level planarity test by Jünger, Leipert, Mutzel 1999.
| Item Type: | Preprint |
|---|---|
| Classifications: | M Methods > M.500 Layered G Algorithms and Complexity > G.490 Embeddings P Styles > P.480 Layered P Styles > P.540 Planar |
| ID Code: | 15 |
| Deposited By: | GDEA, Administration |
| Deposited On: | 15 Sep 2003 |
| Last Modified: | 18 Sep 2008 13:08 |
| Alternative Locations: | http://www.zaik.uni-koeln.de/%7Epaper/preprints.html?show=zaik1999-374 |
Available Versions of this Item
- Level Planar Embedding in Linear Time. (deposited 23 Nov 2004)
- Level Planar Embedding in linear Time. (deposited 15 Sep 2003) [Currently Displayed]
Repository Staff Only: item control page
