FWF - CPGG - Combinatorial Problems on Geometric Graphs

Computational Geometry is a relatively young and very active field of research in the intersection of mathematics and theoretical computer science. Studying algorithms and data structures have been main objectives of this growing discipline. Although geometric graphs are structures defined by geometric properties, like x- and y-coordinates, they have a highly discrete nature. Straight lines spanned by a finite set of discrete points give rise to simple and memory efficient data structures. While not loosing the geometric information, geometric graphs additionally provide combinatorial context (like neighborhood information) that is sufficient for many applications and allows for very efficient and stable algorithms. Moreover, for many problems the geometric information is not needed for their solution. In these cases, point sets, geometric in principle, can be stored and used in a purely combinatorial way. A simple example is the construction of the convex hull of a point set, which is an intrinsic task of countless algorithms. For this it is sufficient to know for any triple a,b,c of points whether c is to the left or to the right of the straight line spanned by a and b. A data structure that stores this information is the so called order type. Not to be forced to rely on geometric information has one major advantage: It enables for simple, exact, and robust algorithms. For these reasons, Computational Geometry has become highly interweaved with fields of Discrete Geometry like Combinatorial Geometry. In the proposed project we want to explore a group of interrelated questions that can be reduced to purely combinatorial problems. One exception from this group of purely combinatorial problems is the question of blocking Delaunay triangulations on bi-colored point sets. The order type does not provide the Delaunay property for quadruples of points, an in-circle property needed for Delaunay triangulation construction. An extended order type, for instance, a “Delaunay order type” mapping the Delaunay property to purely combinatorial data, could help solving this and many other problems on Delaunay triangulations by answering how many different Delaunay triangulation exist for a given “classical” order type. But even though not of pure combinatorial nature, this subproblem is related to the other proposed problems. General methods on bi-colored point sets can be applied to the problems on compatible geometric graphs, isomorphic plane geometric graphs, questions on k-convexity, and also, of course, the Erdős-Szekeres type problems on bi-colored point sets. Further, new insights and results on any of these problems will have implications on the whole project and also to many other problems from Discrete & Computational Geometry. In the context of this project, examples for interesting classes of geometric graphs are triangulations, pseudo-triangulations, spanning trees, spanning circles, spanning paths, and (perfect) matchings. As already mentioned, the proposed problems are interrelated parts of one project. It is our strong belief that attacking these problems in a combined attempt will have synergetic effects to all parts. This will help to make considerable progress on the presented questions, to gain additional insight into their structure, and to finally answer at least some of them.