Radiale Level-Planarität und -Einbettung in Linearzeit
| dc.contributor.author | Bachmeier, Christian | |
| dc.contributor.editor | Wagner, Dorothea | |
| dc.date.accessioned | 2017-09-22T20:42:44Z | |
| dc.date.available | 2017-09-22T20:42:44Z | |
| dc.date.issued | 2005 | |
| dc.description.abstract | Ein Graph mit einer geordneten k-Partitionierung seiner Knoten ist radial level-planar, wenn es eine strikte Auswärtszeichnung auf k konzentrische Kreise ohne Kreuzungen gibt. Radiale Level-Planarität ist eine Erweiterung von Level-Planarität, bei der die Knoten auf k horizontalen Linien und die Kanten strikt nach unten ohne Kreuzungen gezeichnet werden. Kennzeichnend für die Erweiterung sind Ringe, d. h. nicht level-planare zweifache Zusammenhangskomponenten. Unsere Hauptergebnisse sind Linearzeitalgorithmen zum Test auf radiale Level- Planarität und zur Berechnung einer Einbettung. Wir führen die Datenstruktur PQR- Baum ein, bei der die neuen R-Knoten und die dazugehörigen Templates für die korrekte Behandlung von Ringen sorgen. Unsere Algorithmen sind daher eine Erweiterung von hoch entwickelten Level-Planaritätsund -Einbettungs-Algorithmen auf Ba- sis von PQ-Bäumen. | de |
| dc.identifier.isbn | 978-3-88579-409-8 | |
| dc.identifier.pissn | 1617-5468 | |
| dc.identifier.uri | https://dl.gi.de/handle/20.500.12116/4507 | |
| dc.language.iso | de | |
| dc.publisher | Gesellschaft für Informatik | |
| dc.relation.ispartof | Ausgezeichnete Informatikdissertationen 2004 | |
| dc.relation.ispartofseries | Lecture Notes in Informatics (LNI) - Dissertations, Volume D-5 | |
| dc.title | Radiale Level-Planarität und -Einbettung in Linearzeit | de |
| gi.citation.endPage | 28 | |
| gi.citation.publisherPlace | Bonn | |
| gi.citation.startPage | 19 |
Dateien
Originalbündel
1 - 1 von 1