k-Contact Representations

On this website we provide some examples to illustrate the algorithm from Equiangular polygon contact representations by Stefan Felsner, Hendrik Schrezenmaier, and Raphael Steiner. The input to this algorithm is a maximal planar graph with k vertices on the outer face (these graphs are also known as inner triangulations of a k cycle). The goal is to compute a contact representation where each inner vertex is represented by a regular k-gon and the vertices of the outer face correspond to the sides of the circumscribed k-gon.

The implementation and the website, in particular the generated pictures, are due to Hendrik Schrezenmaier and Manfred Scheucher.

Below on this page you find static pictures of contact representations with k-gons. By clicking on the respective images you get to a page where the iterative computation is visualized. The slider (green bullet) on the top of these pages allows to move through the stages of the computation. When the slider is on the right you see the contact representation. The continuous motion is obtained by linear interpolation between consecutive stages in the computation.
Have fun.

Some examples

k=3

k=5

k=7

k=11

k=15

Irregular polygons

k=5

k=7

k=9

The number of iterations

The following graph classes for k=3 and k=5 show that the number of iterations is at least linear in the worst case.

Maximal (known) numbers of iterations:

k=3, n=5: 2 iterations

k=3, n=6: 3 iterations

k=3, n=7: 4 iterations

k=3, n=8: 5 iterations

k=5, n=4: 5 iterations

k=5, n=5: 6 iterations

k=5, n=6: 8 iterations

k=5, n=7: 9 iterations

k=5, n=8: 10 iterations