Radiales und zyklisches Zeichnen von Graphen: Layouts auf dem Zylinder
Final Report Abstract
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.
Publications
- 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at https://dx.doi.org/10.1007/978-3-642-34611-8_13)
