max planck institut

informatik

informatik

You are on the companion page to my 2014 Erasmus Lecture. It was delivered at the 2014 Annual Meeting of the Academia Europaea in Barcelona.

- Slides
- Article based on the Talk, to appear in European Review, Cambridge University Press
- K5 is not planar, under construction
- Planarity Demo without Certificate:
In this demo, I generate random graphs with 11 vertices and 19 edges. Some of these graphs are planar (can be drawn without edge crossings) and some are not. I test each graph for planarity and show the result of the test in a text message. No further explanatation is given.

It is a fairly lengthy video and you should get bored and suspicous after a while. You should start to wonder whether the answers given by the program are correct.

- Planarity Demo with Certificate
This is essentially the same video as in the preceeding item. However, now the program justifies its answers. If it declares a graph planar, it morphes it into a planar drawing of the graph. If if declares a graph non-planar, it exhibits a Kuratowski subgraph. The item ``K5 is not planar'' tries to convince you that the complete graph on five vertices is not planar.

- Video, Part I,under construction
- Video, Part II, under construction
- Video, Part III, under construction
- Ideen der Informatik

Search MPII (type **?** for help)