# Level Planar Embedding in linear Time (Extended Abstract)

Jünger, Michael and Leipert, Sebastian
(1999)
*Level Planar Embedding in linear Time (Extended Abstract).*
**Published In:**
Graph drawing : 7th international symposium ; proceedings / GD '99, Stiřín Castle, Czech Republic, September 1999, Lecture Notes in Computer Science. 1731 Springer 1999, pp. 72-81.

## Abstract

In a level directed acyclic graph G = (V,E) the vertex set V is partitioned into k <= |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) mid x in mathbb{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 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.

Download: |
Postscript
- Preprinted Version
Download (342kB) | Preview |
---|---|

Editorial actions: |
View Item (Login required) |

Item Type: | Proceedings article |
---|---|

Citations: |
No citation data. |

Uncontrolled Keywords: | hierarchies level planar embedding level planar graph PQ-trees |

Subjects: | |

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

Related URLs: |

ZAIK Number: | zaik1999-357 |
---|---|

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

Date Deposited: | 04 Jul 2003 00:00 |

Last Modified: | 16 Jan 2012 14:43 |

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