# Level Planar Embedding in Linear Time (Full Version)

Jünger, Michael and Leipert, Sebastian
(2002)
*Level Planar Embedding in Linear Time (Full Version).*
**Published in: **
Journal of Graph Algorithms and Applications Vol. 6 (1).
pp. 67-113.

## 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.

Download: |
Postscript
- Preprinted Version
Download (1MB) | Preview |
---|---|

Editorial actions: |
View Item (Login required) |

Item Type: | Article |
---|---|

Citations: |
No citation data. |

Uncontrolled Keywords: | graph drawing level planar embedding level planarity PQ-trees |

Subjects: | |

Divisions: | Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger |

Related URLs: |

ZAIK Number: | zaik1999-374 |
---|---|

Depositing User: | Prof. Dr. Michael Jünger |

Date Deposited: | 08 May 2003 00:00 |

Last Modified: | 12 Jan 2012 11:55 |

URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/374 |