Cyclic Level Drawings of Directed Graphs

The Sugiyama framework proposed in the seminal paper of 1981 is one of the most important algorithms in graph drawing and is widely used for visualizing directed graphs. In its common version, it draws graphs hierarchically and, hence, maps the topological direction to a geometric direction. However, such a hierarchical layout is not possible if the graph contains cycles, which have to be destroyed in a preceding step. In certain application and problem settings, e.g., bio sciences or periodic scheduling problems, it is important that the cyclic structure of the input graph is preserved and clearly visible in drawings. Sugiyama et al. also suggested apart from the nowadays standard horizontal algorithm a cyclic version they called recurrent hierarchies. However, this cyclic drawing style has not received much attention since. In this thesis we consider such cyclic drawings and investigate the Sugiyama framework for this new scenario. As our goal is to visualize cycles directly, the first phase of the Sugiyama framework, which is concerned with removing such cycles, can be neglected. The cyclic structure of the graph leads to new problems in the remaining phases, however, for which solutions are proposed in this thesis. The aim is a complete adaption of the Sugiyama framework for cyclic drawings. To complement our adaption of the Sugiyama framework, we also treat the problem of cyclic level planarity and present a linear time cyclic level planarity testing and embedding algorithm for strongly connected graphs.

Level thesis:degree_level

thesis.doctoral

Grantor dc:publisher

Universität Passau

Year

2010

Author dc:creator

• Brunner, Wolfgang

Contributors dc:contributor

• Brandenburg, Franz-Josef

• Ebenenzeichnung
• zyklisch
• graph drawing
• directed graph
• cyclic level drawing
• cyclic level planarity

Statement dc:rights

• Standardbedingung laut Einverständniserklärung

Repository record source_url

https://opus4.kobv.de/opus4-uni-passau/frontdoor/index/index/docId/122

OAI identifier oai:identifier

oai:kobv.de-opus4-uni-passau:122