Universität zu Köln

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

Preview

PDF zaik1999-374.pdf - Draft Version Download (613kB) | Preview

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:	Article
Creators:	Creators Email ORCID ORCID Put Code Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Leipert, Sebastian UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-548509
Journal or Publication Title:	Journal of Graph Algorithms and Applications
Volume:	6
Number:	1
Page Range:	pp. 67-113
Date:	2002
Publisher:	Brown University
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54850