Dagstuhl Seminar Wiki
- Dagstuhl Seminar Wiki (Use personal credentials as created in DOOR to log in)
- The Flip Diameter of Rectangulations and Convex Subdivisions : article in LNCS 8392 LATIN 2014 : pp. 478-489 - Ackerman, Eyal; Allen, Michelle M.; Barequet, Gill; Löffler, Maarten; Mermelstein, Joshua; Toth, Csaba D. - Berlin : Springer, 2014. - pp. 478-489 - (Lecture notes in computer science : 8392 ; article).
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.