Seminar Graphen Zeichnen Sommersemester 2005 Prof. Stefan Felsner Sprechstunde n.V. LV-Nr.: 0230 L 316

Themen:

• Planaritätstests
  • Hopcroft Tarjan (im Buch Appendix A)
  • W. K. Shih and W. L. Hsu, A new planarity test, Theoretical Computer Science 223, (1999), 179-191
    Von Robin Thomas ausgearbeitet in planarity.ps
  • J. Boyer and W. Myrvold. Stop minding your P's and Q's: A simplified O(n) planar embedding algorithm. Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 140-146, 1999. boyer.ps
    A journal version has been submitted boyer-full.ps
  (Mirjana Kolobaric)
  
  
• Konvexe Zeichnungen
  • Auf der Basis von Schnyder Woods, N. Bonichon, S. Felsner und M. Mosbah: Convex Drawings of 3-Connected Plane Graphs .
  (Florian Zickfeld)
  
  
• Rechtwinklige Zeichnungen (im Buch Kap 8)
  • Kapitel 8 aus dem Buch Planar Graph Drawing von Nishizeki und Rahman.
  • Kapitel 5 aus Graph Drawing: Algorithms for the Visualization of Graphs by Tollis, Di Battista, Eades and Tamassia.
  (Steffen Melang)
  
  
• Buch Einbettungen
  • D. Wood, Bounded-Degree Book Embedings
  (Mareike Massow)
  
  
• Zeichnen von Ordnungen, eine Heuristik
  • The Linear-Extension-Diameter of a Poset S. Felsner und K. Reuter, SIAM Journal on Discrete Mathematics 12 (1999), 360-373.
  (Nina Siebold)
  
  
• Zeichnen von Verbänden
  • R. Freese, Automated Lattice Drawing, Lecture Notes in Artificial Intelligence, 2961, Springer, Berlin, 2004, 112-127. PDF-version
    DEMO page
  • Drawing concept lattices, Wille.
  (Patrick Baier)
  
  
• A successful concept for measuring non-planarity of graphs: the crossing number
  László Székely
  (Stephan Hell)
  
  
• New Theoretical Bounds of Visibility Representation of Plane Graphs
  Huaming Zhang und Xin He, Graph Drawing 2004: Springer LNCS Band 3383, Ed. Janos Pach.
  (Kamil Kloch)
  
  
• Contact and Intersection Representations
  Hubert de Fraysseix und Patrice Ossona de Mendez, Graph Drawing 2004: Springer LNCS Band 3383, Ed. Janos Pach.
  (Cornelia Dangelmayr)
  
  
• Intersection reverse sequences and geometric applications
  Adam Marcus und Gabor Tardos, Graph Drawing 2004: Springer LNCS Band 3383, Ed. Janos Pach.
  (Sarah Kappes [geb. Renkl])