Circle Planarity of Level Graphs
Kreisplanarität von Level-Graphen
- In this dissertation we generalise the notion of level planar graphs in two directions: track planarity and radial planarity. Our main results are linear time algorithms both for the planarity test and for the computation of an embedding, and thus a drawing. Our algorithms use and generalise PQ-trees, which are a data structure for efficient planarity tests.
- In dieser Arbeit wird der Begriff Level-Planarität von Graphen auf zwei Arten erweitert: Spur-Planarität und radiale Level-Planarität. Die Hauptergebnisse sind Linearzeitalgorithmen zum Testen dieser Arten von Planarität und zur Erstellung einer entsprechenden Einbettung und somit einer Zeichnung. Die Algorithmen verwenden und generalisieren PQ-Bäume, eine bei effizienten Planaritätstests verwendete Datenstruktur.
Download full text files
Additional Services
| Author: | Christian Bachmaier |
|---|---|
| URN: | urn:nbn:de:bvb:739-opus-385 |
| Advisor: | Franz J. Brandenburg |
| Document Type: | Doctoral Thesis |
| Language: | English |
| Year of Completion: | 2004 |
| Date of Publication (online): | 2004/07/15 |
| Publishing Institution: | Universität Passau |
| Granting Institution: | Universität Passau, Fakultät für Informatik und Mathematik |
| Date of final exam: | 2004/07/09 |
| Release Date: | 2004/07/15 |
| Tag: | radial level panarity; track planarity |
| GND Keyword: | Graphentheorie; Graphenklasse; Graphenzeichnen; 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 |
