Logo des Repositoriums
 
Textdokument

Neue Anwendungen von SPQR-Bäumen im Graphenzeichnen

Lade...
Vorschaubild

Volltext URI

Dokumententyp

Zusatzinformation

Datum

2003

Zeitschriftentitel

ISSN der Zeitschrift

Bandtitel

Verlag

Gesellschaft für Informatik

Zusammenfassung

Wir untersuchen zwei Probleme auf dem Gebiet des Zeichnens von Gra- phen. Bei beiden Problemen geht es darum, eine Funktion über der Menge aller Einbettungen eines planaren Graphen zu optimieren und wir verwenden jeweils SPQR- Bäume um die Probleme zu lösen. Das erste von uns betrachtete Problem ist das Einfügen einer zusätzlichen Kante in einen planaren Graphen mit möglichst wenigen Kreuzungen. Dies is der erste Algorithmus, der das Problem löst und er hat lineare Laufzeit. Das zweite Problem ist das Berechnen einer orthogonalen Zeichnung mit der minimalen Anzahl von Knicken. Es ist bekannt, dass dieses Problem NP-schwer ist. Hier benutzen wir den SPQR-Baum, um ein ganzzahliges lineares Programm zu entwickeln, dessen Lösungen den Einbettungen des Graphen entsprechen. Dies ist die Grundlage für unseren Algorithmus für die Berechnung einer knick-minimalen Zeichnung, der sich in unseren Experimenten im Vergleich mit der bisher verwendeten Methode überlegen gezeigt hat.

Beschreibung

Weiskircher, René (2003): Neue Anwendungen von SPQR-Bäumen im Graphenzeichnen. Ausgezeichnete Informatikdissertationen 2002. Bonn: Gesellschaft für Informatik. PISSN: 1617-5468. ISBN: 978-3-88579-407-1. pp. 201-210

Schlagwörter

Zitierform

DOI

Tags