March 10 – 13 , 2013, Event 13112

Counting and Enumerating of Plane Graphs


Kevin Buchin (TU Eindhoven, NL)
André Schulz (Universität Münster, DE)
Csaba Tóth (University of Calgary, CA)

For support, please contact

Heike Clemens


Dagstuhl's Impact: Documents available
Event Wiki

(Use seminar number and access code to log in)


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.

Online Publications

We offer several possibilities to publish the results of your event. Please contact publishing(at) if you are interested.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf in the library.