Logo des Repositoriums
 
Textdokument

Radiale Level-Planarität und -Einbettung in Linearzeit

Lade...
Vorschaubild

Volltext URI

Dokumententyp

Zusatzinformation

Datum

2005

Zeitschriftentitel

ISSN der Zeitschrift

Bandtitel

Verlag

Gesellschaft für Informatik

Zusammenfassung

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.

Beschreibung

Bachmeier, Christian (2005): Radiale Level-Planarität und -Einbettung in Linearzeit. Ausgezeichnete Informatikdissertationen 2004. Bonn: Gesellschaft für Informatik. PISSN: 1617-5468. ISBN: 978-3-88579-409-8. pp. 19-28

Schlagwörter

Zitierform

DOI

Tags