10. – 13. März 2013, Event 13112

Counting and Enumerating of Plane Graphs


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

Auskunft zu diesem Event erteilt

Heike Clemens


Dagstuhl's Impact: Dokumente verfügbar
Event Wiki

(Zum Einloggen bitte Seminarnummer und Zugangscode verwenden)


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.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact aufgelistet und separat in der Bibliothek präsentiert.