Günter Rote -Freie Universität Berlin

Strictly convex drawing of a planar graph

Abstract: Every three-connected planar graph with n vertices has a drawing on an O(n^7/3)xO(n^7/3) grid in which all faces are strictly convex polygons. In proving this result, I will review the different approaches for obtaining a graph drawing with convex faces (not necessarily strictly convex) on a grid of linear side length, going back to Schnyder and to de Fraysseix, Pach, and Pollack, respectively.

I will discuss the number-theoretic problem that is involved in perturbing a convex polygon into a strictly convex polygon, and related questions of realizing convex polygons and convex polytopes on small integer grids.

Colloquium - 16:00

Esther Moet -Utrecht University

Guarding Art Galleries by Guarding Witnesses

Abstract: The so-called Art Gallery Problems form an important subcategory within the Computational Geometry. In my talk, we look at the following problem: "Given a polygon P, does it admit a witness set, i.e., a set of points in P such that any (prospective) guard set that guards the witnesses is guaranteed to guard the whole polygon?" The idea, of course, is that in the case of a set of moving guards, or of a guard set that permits the addition or removal of guards, it is easier to check point-to-point (i.e., guard-to-witness) visibility, than to update the complete visibility region of all guards. We show that not all polygons admit a finite witness set and prove several other combinatorial properties of finite witness sets. We give an algorithm to compute a minimum size witness set for P in O(n² log n) time, if such a set exists, or to report the non-existence within the same time bounds. We also outline an algorithm that use a witness set for P to test whether a (prospective) guard set sees all points in P.