Universität zu Köln

Jünger, Michael and Leipert, Sebastian (1999). Level Planar Embedding in linear Time (Extended Abstract). Springer. ["eprint_fieldopt_monograph_type_preprint" not defined].

Preview

PDF zaik1999-357.pdf Download (280kB) | Preview

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.

Item Type:	Preprints, Working Papers or Reports (["eprint_fieldopt_monograph_type_preprint" not defined])
Creators:	Creators Email ORCID ORCID Put Code Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Leipert, Sebastian UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-548410
Series Name:	Lecture Notes in Computer Science
Volume:	1731
Page Range:	pp. 72-81
Date:	1999
Publisher:	Springer
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/54841