Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, June 11, 2015, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Manuel Wettstein
We define the notion of a trapezoidal diagram of a plane graph G (embedded without crossings on a planar point set). Informally speaking, such a diagram is obtained by augmenting G with its trapezoidal decomposition and then forgetting about the exact locations of the vertices.
We study the number of such diagrams if the graphs G are either (a) perfect matchings or (b) triangulations. In both cases we give bijective proofs that establish certain relations with so called 3-dimensional Catalan numbers. We determine the exponential growth rates of the number of such diagrams as A^n and B^n, respectively, where n is the number of vertices, A = sqrt(27) = 5.196, and B = 27 / (729 * sqrt(3) / (40 * pi) - 9)^3 = 23.459.
Coincidentally, the number of such diagrams in the case of perfect matchings is equal to the number of different ways (in terms of the vertical visibility structure) that we can arrange n/2 non-intersecting convex shapes in the plane. In the case of triangulations, these diagrams are closely related to upward triangulations (i.e., directed maximal planar graphs that allow a plane embedding in which all edges are drawn as y-monotone curves pointing upwards).
Automatic MiSe System Software Version 1.4803M | admin login