Themen und Vorlesungen 
Lecture #0: Organisational matters 


Lecture #0: Organisational matters 


Lecture #1: Introduction 


Lecture #1: Introduction kurz 


Lecture video #1a: Introduction 


Lecture #1: Examples 


Lecture video #1b: Examples 


Lecture #1: Divide and Conquer Algorithms for Trees and SeriesParallel Graphs 


Lecture #1: Divide and Conquer Algorithms for Trees and SeriesParallel Graphs kurz 


Lecture video #1c: Trees, levelbased layout 


Lecture video #1d: hvdrawings 


Lecture video #1e: radial layout 


Lecture video #1f: Seriesparallel graphs 


Lecture #2: Planar straightline drawings with shift method 


Lecture #2: Planar straightline drawings with shift method short 


Lecture video #2a: Canonical order 


Lecture video #2b: Shift method 


Lecture #3: Planar straightline drawings with Schnyder realiser 


Lecture #3: Planar straightline drawings with Schnyder realiser short 


Lecture video #3a: Planar straightline drawings with Schnyder realiser 


Lecture video #3b: Planar straightline drawings with Schnyder realiser 


Lecture #4: Orthogonal layouts 


Lecture #4: Orthogonal layouts short 


Lecture video #4a: Orthogonal layouts intro 


Lecture video #4b: Orthogonal representations 


Lecture video #4c: Orthogonal drawings 


Lecture video #4d: Orthogonal compaction NPhardness 


Lecture #5: Upward planar drawings 


Lecture #5: Upward planar drawings short 


Lecture video #5a: Upward planar drawings intro 


Lecture video #5b: Upward planar drawings 


Lecture #6: Hierarchical layouts 


Lecture #6: Hierarchical layouts short 


Lecture #7: Contact representations 


Lecture #7: Contact representations short 


Lecture #8: The Crossing Lemma 


Lecture #8: The Crossing Lemma short 


Lecture #9: Forcedirected algorithms 


Lecture #9: Forcedirected algorithms short 


Lecture #10: SPQRtrees and Partial Bar Visibility Representation Extension 


Lecture #10: SPQRtrees and Partial Bar Visibility Representation Extension short 


Lecture #11: Octilinear graph drawing of metro maps 


Lecture #11: Octilinear graph drawing of metro maps short 


Übungen und Übungsblätter 
LaTeX template for exercise sheets 


Literatur und zusätzliche Materialien 
Lecture #1 [Reingold and Tilford 1981] Tidier Drawings of Trees 


Lecture #1 [Supowit and Reingold 1983] The complexity of drawing trees nicely 
This paper shows that one can use LPbased methods to minimize the width of a "balancedlayered" drawing of tree, but if one desires a grid drawing the problem becomes NPhard. 

Lecture #3 [Schnyder 1990] Embedding Planar Graphs on the Grid 


Lecture #4 [Patrignani 2001] On the complexity of orthogonal compaction 
Lecture #3: reference for the NPhardness proof regarding optimally "compactifying" an orthogonal drawing of an embedded graph. 

Lecture #7 [de Fraysseix, de Mendez, Rosenstiehl 1994] On Triangle Contact Graphs 


Lecture #7 [He 1993] On Finding the Rectangular Duals of Planar Triangular Graphs 


Lecture #7 [Kant and He 1994] Two algorithms for finding rectangular duals of planar graphs 


Lecture #8 [Székely 1997] Crossing numbers and hard Erdős problems in discrete geometry 
This paper contains several applications of the crossing lemma. Be warned that the presentation is a bit dense at times. 

Lecture #8 [Bienstock and Dean 1993] Bounds for rectilinear crossing numbers 


Lecture #8 [Schaefer 2020] The Graph Crossing Number and its Variants: A Survey 


Lecture #8 Terry Tao's blog on Crossing Numbers 
Terry Tao's blog entry on the crossing inequality.


Lecture #8 Movie "N Is a Number: A Portrait of Paul Erdös" 


Lecture #9 Web interface for forcedirected approaches 
This website gives a live demo environment (with configurable constants) and many example graphs drawn via forcedirected methods. 

Lecture #10 [CGGKL18] The Partial Visibility Representation Extension Problem 


Lecture #11 [Nöl14] A Survey on Automated Metro Map Layout Methods 
