Combinatorics of Point Sets and Arrangements of Objects
Final Report Abstract
During the first half of EuroGIGA, ComPoSe and cross-CRP meetings and workshops have significantly enhanced the collaborations between the teams. The ComPoSe project is clearly boosting discrete geometry in Europe, and moving the center of gravity of research in this field towards Europe. See http://www.eurogiga-compose.eu for a list of events and participants for each event, and for a list of publications which came up from these collaborations. Thus, EuroGIGA and the ComPoSe CRP clearly have been a great catalyser for all participating groups, which by itself we consider a valuable and lasting highlight for our community. One of the scientific highlights of the ComPoSe research was the proof of NP-hardness of the clique problem in segment intersection graphs, a long-standing problem posed by Kratochvil (CRP GraphDr) and Nesetril in 1992. Another NP-hardness result contributes towards the 25 year old conjecture that computing the optimal sequence of edge flips in convex polygons is NP-hard, a problem which is equivalent to the rotation distance of binary trees. A venture that involved several IPs, as well as other CRPs, is investigating the rotation system of point sets. A strong connection to the realm of order types was observed. Extensive future collaboration on the relation between order types, rotation systems and related structures is planned. A breakthrough for the crossing number of drawings of complete graphs for 2-page book drawings has already been reported in the midterm report. Within ComPoSe, this work was extended to a wider range of complete graphs. There, the notion of shellability of a drawing D of the complete graph K_n is introduced. It is shown that if D is sufficiently s-shellable, then the Harary-Hill conjecture holds for D. After over 50 years of research on this conjecture the first combinatorial condition on a drawing is presented that guarantees that the conjecture is true for this drawing. The team around Pavel Valtr could recently show new results on the Erdős-Szekeres theorem (a central topic in the CRP) with forbidden subconfigurations. In collaboration with GraDR Stefan Felsner’s paper on “Exploiting Air-Pressure to Map Floorplans on Point Sets” is also a highlight; and a generalized concept of geometric convexity. “On k-convex polygons” combines nicely the combinatorial expertise of several ComPoSe members with the geometric/algorithmic knowledge within VORONOI; the concept was also successfully applied to point sets. Cibulka, Kyncl and Valtr investigate properties of planar point sets (not necessarily in general position) with no 5-hole. A counterexample to the famous Hirsch conjecture has been obtained during the preparation of this CRP. In that connection, F. Santos received the Humboldt Research Award in Nov. 2012. A series of papers on proximity graphs has also attracted researchers from GraDR. The massive collaboration on discrete point sets has helped to identify common properties of these sets which are relevant in different fields of research. This started a joint collection of discrete point sets with interesting (extreme) properties, which can be used to efficiently check conjectures, find counterexamples or improve lower/upper bounds. This collection has to a large extent been set up and has been made publicly available. It is expected that this free data base of discrete point sets will be used by many researches in the field. Similar data bases work already very well, e.g. in Computer Vision or Graph drawing. A book with thirty contributions to geometric graph theory has been edited by J. Pach (AP): "Thirty Essays on Geometric Graph Theory. Algorithms and Combinatorics”, 2013.
Publications
- Coloring Planar Homothets and Three-Dimensional Hypergraphs. LATIN 2012: 121-132
Jean Cardinal and Matias Korman
(See online at https://doi.org/10.1007/978-3-642-29344-3_11) - On k-convex polygons. Computational Geometry. Vol. 45, pp. 73-87, 2012
O. Aichholzer, F. Aurenhammer, E. D. Demaine, F. Hurtado, P. Ramos, and J. Urrutia
(See online at https://doi.org/10.1016/j.comgeo.2011.09.001) - Non-crossing matchings of points with geometric objects. Comput. Geom. 46(1): 78-92 (2013)
Greg Aloupis, Jean Cardinal, Sébastien Collette, Erik D. Demaine, Martin L. Demaine, Muriel Dulieu, Ruy Fabila Monroy, Vi Hart, Ferran Hurtado, Stefan Langerman, Maria Saumell, Carlos Seara, and Perouz Taslakian
(See online at https://doi.org/10.1016/j.comgeo.2012.04.005) - Bend-optimal orthogonal graph drawing in the general position model, Comput. Geom. 47: 460-468 (2014)
S. Felsner, M. Kaufmann, and P. Valtr
(See online at https://doi.org/10.1016/j.comgeo.2013.03.002) - Shellable drawings and the cylindrical crossing number of K_n. Discrete & Computational Geometry 52 (2014), 743-753
B. M. Ábrego, O. Aichholzer, S. Fernández-Merchant, P. Ramos, and G. Salazar
(See online at https://doi.org/10.1007/s00454-014-9635-0)
