AG 1, AG 2, AG 3, AG 4, AG 5, SWS   Info

AG Audience

English

45 Minutes

Saarbrücken

Planar graphs form an important subset of general graphs. While it is easy to sample a general graph uniformly at random (choose each edge independently with probability 1/2), it is not obvious how to generate a random sample of a planar graph efficiently. We will see an approach to sample planar graphs based on a recursive decomposition of planar graphs along their connectivity structure. In this decomposition 3-connected planar graphs form the basic building blocks.

We will discuss how such a recursive decomposition scheme can be transformed to a uniform sampling algorithm and how we can apply generating functions to speed up the calculations involved.

Martin Kutz

--email hidden

passcode not visible

logged in users only

Graph Theory; Algorithms