---

Time & Place

Lecture: Monday 10:15-12:00 and Thursday 09:15-10:00 CAB G59. The lecturers are:
Exercise Class: Thursday 14:15-16:00, CHN D44. The teaching assistant is:

Contents

• Course material
• Course description
• Procedures, exercises, exam
• Complementary courses
• Further literature and links

Schedule

The exact schedule will be updated on a weekly basis.

Calendar Week	Date	Topic	Exercises	Material
8	Mon Feb 20	Introduction	Exercise 1	Introduction slides (part 1)
	Thu Feb 23	Planarity		Introduction slides (part 2)
9	Mon Feb 27	Planarity and Canonical ordering	Exercise 2 Homework 1 (due: Sun Mar 18)	Introduction slides (part 3) Whitney's Theorem and Fary's Theorem Exercise 2: nested triangles example
	Thu Mar 1	Canonical ordering and the Shift algorithm
10	Mon Mar 5	Shift algorithm	Exercise 3	Canonical ordering and the Shift algortihm
	Thu Mar 8	Tutte spring embeddings		Tutte spring embeddings
11	Mon Mar 12	History of the Catalan numbers	Exercise 4 Homework 1 due on Sun Mar 18	History of the Catalan numbers
	Thu Mar 15	Counting triangulations		Random triangulations of planar point sets Solutions to Exercise 4
12	Mon Mar 19	Counting triangulations	Exercise 5
	Thu Mar 22	Counting triangulations
13	Mon Mar 26	Counting triangulations	Homework 2 (due: Wed Apr 18) Exercise 6
	Thu Mar 29	Crossing lemma		Lecture notes of Michiel Smid
14	Mon Apr 2	Crossing lemma Counting plane graphs	Exercise 7	Counting plane graphs Solutions to Exercise 7
	Thu Apr 5	Counting plane graphs
15	Mon Apr 9	Easter holidays: no lecture
	Thu Apr 12	Easter holidays: no lecture
16	Mon Apr 16	Counting spanning cycles	Exercise 8 Homework 2 due on Wed Apr 18	Counting plane graphs: Perfect Matchings, Spanning Cycles and Kasteleyn's Technique
	Thu Apr 19	Counting spanning cycles
17	Mon Apr 23	Intersection graphs (I): Intervals and Permutations	Exercise 9 Graded talk (Homework 2) on Thu Apr 26 at 14:15	Intersection graphs (I): Intervals and Permutations
	Thu Apr 26	Intersection graphs (Ib): Rectangles and Boxes		Intersection graphs (Ib): Rectangles and Boxes
18	Mon Apr 30	Lines and Pseudolines	Exercise 10 Homework 3 (due: Sun May 13)	Lines and Pseudolines Number of Faces in Arrangements String graphs requiring exponential representations
	Thu May 3	String graphs requiring exponential representations
19	Mon May 7	Kissing disks theorem	Exercise 11 Homework 3 due on Sun May 13	Intersection graphs (II): Strings and Disks Kissing Disks Theorem Königs Theorem (see Theorem 2.1.1, page 30)
	Thu May 10
20	Mon May 14
	Thu May 17	Ascension Day: no lecture
21	Mon May 21		Exercise 12 (TBA)
	Thu May 24
22	Mon May 28	Pentecost: no lecture
	Thu May 31

Course Description

The theory of geometric graphs is located somewhere in the intersection of graph theory, combinatorial geometry, and algorithmics. It is is concerned with embeddings of graphs, specifically into the Euclidean plane.

The goal of this lecture is twofold: On one hand, to provide a certain breadth in order to make students familiar with the most important techniques and results in the area. Armed with this knowledge, students should be able to solve typical problems that are related to or can be modeled using geometric graphs. On the other hand, we want to selectively go into more depth with some topics, specifically those that are closely related to current research activities within the group (such as counting, enumerating and sampling crossing-free configurations, coloring problems, and simultaneous embeddings of graphs). Therefore, this lecture forms an ideal starting point for a project or thesis in the area.

Fundamental questions of interest are: Which properties are desirable for an embedding? Under which conditions do certain types of embeddings exist? If so, can these conditions be tested for efficiently? Can a certain type of embedding be constructed efficiently? How many embeddings of a certain type do exist? Within this lecture we will discuss some of the most important directions and results in the area, a few classic and others very recent.

Procedures, exercises, exam

Every week we provide you with an exercise sheet. You should solve it in written form and return your solutions the week after. Your solutions are thoroughly commented and graded, but they do not count towards your final grade. The motivation to work on the exercises stems from your interest in the topic (and possibly also the desire to succeed in the exam :-)).

In Addition, you receive four small projects during the semester. Also these projects are to be solved in written form, but typically you have two weeks of time to return your solutions/reports, typeset in LaTeX. In contrast to the exercises, projects do count towards the final grade: Your three best grades will account for 10% of your final grade each. Solving projects in teams is not allowed.

There is an oral exam of 30 minutes during the examination period. Your final grade consists to 70% of the grade for the exam and to 30% of the grade for the projects.

You are expected to learn proofs discussed in the lecture, should be able to explain their basic ideas and reproduce more details on demand. You should also be able to give a short presentation on any topic treated throughout the course.

One of the questions given to you during the exam is to solve one of the exercises posed throughout the semester.

Roughly half an hour before the exam you get to know the exercise to be solved and one topic that you will be questioned about in particular, that is, you have 30 minutes preparation time. For this preparation, paper and pencil will be provided. You may not use any other material, like books or notes.

For PhD students, the same rules apply for obtaining credit points as for all other participants. Taking the exam and achieving an overall grade of at least 4.0 (computed as a weighted average of grades for special exercises and the written final exam as detailed above) qualifies for receiving credits. In order to comply with new regulations recently issued by the department, merely attending the course and/or handing in exercises is no longer sufficient.

Complementary Courses & Semester/Master/Diploma Theses

This course is complemented by a seminar that takes place every autumn semester. Furthermore, after  having completed the course and the seminar, it is possible to do a semester, master or diploma thesis in the area. Students are also welcome at our graduate seminar.

Literature and Links

• Part of the course is covered by a book of Takao Nishizeki and Md. Saidur Rahman Planar Graph Drawing
• Some topics are covered by Stefan Felsner's book Geometric Graphs and Arrangements: Some Chapters from Combinatorial Geometry
• New to LaTeX? Look at Thomas Rast's excellent LaTeX Tutorial.

---