Graduiertenkollegs

COMBINATORICS, GEOMETRY, AND COMPUTATION (abgelaufen)

METHODS FOR DISCRETE STRUCTURES (beantragt)

[Blockkurse]

Block Course |

**
Embeddings of Planar Graphs**

March 20 - March 31, 2006

**Location**: Institut für Mathematik,

Technische Universität Berlin

Straße des 17. Juni 136,

D-10623 Berlin

The room for the lectures of the second week is

Tutte embeddings and the Maxwell-Cremona correspondence

Chapter 5: Tutte embeddings (pp. 39-50)

Chapter 6: Stresses and reciprocal diagrams (pp. 56-59)

The slides of lectures 10 and 11: Duality for Schnyder Woods, Orthogonal Surfaces and the Lattice of alpha-Orientations.

The slides (fotos) of lecture 12: Circle Packings

The slides of lecture 13: Dimension af Orders, Graphs and Polytopes.

Steffen Melang's notes of lecture 1: Introduction to planar graphs

Mareike Massow's notes of lecture 1: Introduction to planar graphs

Simon Albroscheit's notes of lecture 2: The Hanani-Tutte Theorem

Lars Wolter's notes of lecture 3: Tutte: How to draw a graph

Anna Gundert's notes of lecture 5: Drawing I: Bipolar orientations

Mª del Pilar Sabariego's notes of lecture 5: Drawing I: Bipolar orientations

CONTENTS:

The course will focus on problems at the borderline between graph theory and geometry. Planar graphs are in the center of this active and exciting area. The presentation will start with a general chapter on planar graphs and continue with four chapters on more specific topics:

- Planar Graphs and Polytopes

Steinitz' Theorem -- Tutte embeddings -- The Maxwell-Cremona correspondence.

- Planar Graphs and Orthogonal Surfaces

Graphs and order dimension -- drawings and Schnyder woods -- geometry of orthogonal surfaces.

- Beyond Planarity: Crossings and More

Crossing lemma -- crossing number of K_{n}-- unavoidable configurations -- segment graphs.

- Pseudotriangulations

Rigidity of pseudotriangulations -- expansive motions -- the carpenter's rule problem -- combinatorial pseudotriangulations.

Students who want credit and a grade for the course can take part in an examination at the end of the course. Depending on the number of participants, it will be an oral exam or a written exam.

PREREQUISITES:

Basic knowledge in graph theory

LECTURERS:

Stefan Felsner, Technische Universität Berlin and
Günter Rote, Freie Universität Berlin

The course will be held in English.

REGISTRATION:

Participants should register by sending an email to
Gabriele Klink until March 5, 2006.

SCHEDULE

The daily schedule will consist of two lectures

9:15 - 10:45 and
11:00 - 12:30

and a tutorial to discuss the exercises in the afternoon

16:00 - 17:30

In the first week these lectures will be given in
room MA 141 in the 1st floor of the mathematics building
at technical university (
map of the area). The room is in the first floor just
behind the elevators. We meet there on Monday at 9:00.

There are three additional rooms MA 649, MA 650 and MA 651
which can be used e.g. during the long break to solve the
exercises in groups.

The topics for the first week will be

- Introduction to planar graphs and the Hanani-Tutte Theorem
- Tutte embeddings and the Maxwell-Cremona correspondence
- Bipolar orientations and visibility representations
- Schnyder woods and straight line drawings
- Convex drawings and the Coin-Graph Theorem

[cgc-home] - [top of page] | last updated: March 16, 2006 |