Detailseite
Projekt Druckansicht

Radiales und zyklisches Zeichnen von Graphen: Layouts auf dem Zylinder

Fachliche Zuordnung Theoretische Informatik
Förderung Förderung von 2009 bis 2012
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 148338284
 
Erstellungsjahr 2012

Zusammenfassung der Projektergebnisse

Es ist uns gelungen, das über 25 Jahre offene bzw. unbeachtete Problem des Zeichnens von "recurrent hierarchies" auf dem Niveau des etablierten hierarchischen Verfahrens zu lösen. Entsprechendes gilt für den radialen Fall, bei dem die Ebenen zu konzentrischen Kreisen werden. Diese Visualisierungen sind für soziale Netze relevant. Somit ist festzuhalten: Auch der radiale und der zyklische Fall sind gelöst! Es stehen nun drei Varianten zur Verfügung: hierarchisch in der Ebene, radial mit konzentrischen Kreisen und zyklisch auf dem Zylinder. Darüber hinaus konnten neue Charakterisierungen für die Spezialisierung auf planare Graphen erzielt werden. Diese führen zu aufwärts planaren Graphen auf unterschiedlichen Oberflächen, wie Ebene, Kugel, stehender und rollender Zylinder. Die resultierenden Klassen von Graphen wurden klassifiziert und über ihre Dualgraphen charakterisiert. Schließlich ermöglichen lineare Layouts auf dem Zylinder die intuitive Visualisierung des I/O Verhaltens klassischer Datenstrukturen. So können stacks, queues und deques einfach erklärt werden. Als Highlight ergibt sich die Trennung zwischen zwei stacks und einer deque in Form von Hamilton Kreis und Hamilton Pfad bei planaren Graphen.

Projektbezogene Publikationen (Auswahl)

  • Crossing Minimization in Extended Level Drawings of Graphs. Discrete Applied Mathematics, Vol. 158. 2010, Issue 3, pp. 159–179.
    C. Bachmaier, H. Buchner, M. Forster, S.-H. Hong
    (Siehe online unter https://dx.doi.org/10.1016/j.dam.2009.09.002)
  • Global k-Level Crossing Reduction. Journal of Graph Algorithms and Applications, Vol. 15. 2011, no. 5, pp. 631-659.
    C. Bachmaier, F. J. Brandenburg, W. Brunner, F. Hübner
    (Siehe online unter https://dx.doi.org/10.7155/jgaa.00242)
  • Plane Drawings of Queue and Deque Graphs. Graph Drawing - 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010. Revised Selected Papers. Lecture Notes in Computer Science, Vol. 6502. 2011, pp 68-79.
    C. Auer, C. Bachmaier, F. J. Brandenburg, W. Brunner, A. Gleißner
    (Siehe online unter https://dx.doi.org/10.1007/978-3-642-18469-7_7)
  • Drawing Recurrent Hierarchies. Journal of Graph Algorithms and Applications, Vol. 16. 2012, no. 2, pp. 151-198.
    C. Bachmaier, F. J. Brandenburg, W. Brunner, R. Fülöp
    (Siehe online unter https://dx.doi.org/10.7155/jgaa.00254)
  • Grid Sifting: Leveling and Crossing Reduction. Journal of Experimental Algorithmics (JEA), Vol. 17.2012, Article No. 1.7.
    C. Bachmaier, W. Brunner, A. Gleißner
    (Siehe online unter https://dx.doi.org/10.1145/2133803.2345682)
  • The Duals of Upward Planar Graphs on Cylinders. Graph-Theoretic Concepts in Computer Science - 38th International Workshop, WG 2012, Jerusalem, Israel, June 26-28, 2012, Revised Selcted Papers, Lecture Notes in Computer Science, Vol. 7551. 2012, pp 103-113.
    C. Auer, C. Bachmaier, F. J. Brandenburg, Andreas Gleißner, K. Hanauer
    (Siehe online unter https://dx.doi.org/10.1007/978-3-642-34611-8_13)
 
 

Zusatzinformationen

Textvergrößerung und Kontrastanpassung