OPUS - Passau

Bibliographische Daten und PDF-Volltexte aus der Universität Passau
... die Wissenschaft der Hochschule sichtbar machen!

OPUS-Frontdoor

Bachmaier, Christian

Circle Planarity of Level Graphs

Kreisplanarität von Level-Graphen

Open Access: Freier Zugang zum Volltext!

pdf-Format:

Dokument 1.pdf (1.308 KB)

SWD-Schlagwörter:		Graphentheorie , Graphenklasse , Graphenzeichnen , Graph
Freie Schlagwörter (Englisch):		radial level panarity , track planarity
Beteiligte Einrichtung:		Mitarbeiter Lehrstuhl/Einrichtung der Fakultät für Informatik und Mathematik
Fakultät:		Fakultät für Informatik und Mathematik
DDC-Sachgruppe:		Informatik
Dokumentart:		Dissertation
Hauptberichter:		Brandenburg, Franz J. (Prof. Dr.)
Sprache:		Englisch
Tag der mündlichen Prüfung:		09.07.2004
Erstellungsjahr:		2004
Publikationsdatum:		15.07.2004
Kurzfassung auf Englisch:		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.
Kurzfassung auf Deutsch:		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.

Home

22.10.10