Radiales und zyklisches Zeichnen von Graphen: Layouts auf dem Zylinder

• Applicant: Professor Dr. Franz Josef Brandenburg
• Subject Area: Theoretical Computer Science
• Term: from 2009 to 2012
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 148338284

• Final Report Year: 2012

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
  
• 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
  
• 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
  
• 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
  
• 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
  
• 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