Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Research Meeting 13112

Counting and Enumerating of Plane Graphs

( Mar 10 – Mar 13, 2013 )

(Click in the middle of the image to enlarge)

Please use the following short url to reference this page:


Dagstuhl Seminar Wiki


A plane graph is a geometric representation of a graph where the vertices are realized as points in the plane and the edges as straight-line segments such that segments can intersect only in common endpoints. Plane graphs are fundamental objects, which are often used for modeling the solutions of computational and optimization problems.

Determining the maximum multiplicities of certain classes of plane graphs on a given vertex set is a challenging task. Several new methods have been developed over the last decade culminating in a series of improvements for the bounds of these multiplicities. During the workshop we intend to highlight the newest approaches in this field and discuss new ideas and directions of further research. Furthermore, we would like to develop efficient methods for enumerating plane graphs for given vertex sets, and we are also interested in algorithms that determine the exact number of certain classes of plane graphs without enumeration. Typical classes of plane graphs we consider are spanning cycles (tours), perfect matchings, triangulations, spanning trees, connected graphs, and cycle-free graphs.