## Cyclic Level Drawings of Directed Graphs

### Zyklische Levelzeichnungen gerichteter Graphen

- 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 isThe 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.…

Author: | Wolfgang Brunner |
---|---|

URN: | urn:nbn:de:bvb:739-opus-17962 |

Advisor: | Franz-Josef Brandenburg |

Document Type: | Doctoral Thesis |

Language: | English |

Year of Completion: | 2010 |

Date of Publication (online): | 2010/05/11 |

Publishing Institution: | Universität Passau |

Granting Institution: | Universität Passau, Fakultät für Informatik und Mathematik |

Date of final exam: | 2010/03/17 |

Release Date: | 2010/05/11 |

Tag: | Ebenenzeichnung; zyklischcyclic level drawing; cyclic level planarity; directed graph; graph drawing |

GND Keyword: | Graphenzeichnen; Gerichteter Graph; Kreis <Graphentheorie>; Planarer Graph |

Institutes: | Fakultät für Informatik und Mathematik / Mitarbeiter Lehrstuhl/Einrichtung der Fakultät für Informatik und Mathematik |

Dewey Decimal Classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |

open_access (DINI-Set): | open_access |

Licence (German): | Standardbedingung laut Einverständniserklärung |