WORK PACKAGE 1
Geometric Networks Details
Graphs are characterized according to different criteria, such as number of edges, planarity, connectivity, and many more. In a geometric graph, also the position of the points in the plane matters. For instance, distances between vertices and angles between edges are geometric properties that are relevant for many applications. Many properties of geometric graphs are known, and many well-known geometric graphs like minimum weight spanning trees or Delaunay triangulations are used frequently. However, many important questions on geometric graphs are still open. An important part of this project is about advancing the state of the art of the knowledge about geometric graphs. We illustrate some of the challenges on this topic with three examples that will be studied in CONNECT:
Show many geometric graphs can n points in the plane have? The answer to such a simple question is still not known, despite lots of research for triangulations and other classes of geometric graphs. Some of the best bounds at the moment on this problem were obtained by CONNECT members [AAHPSV16, AHHHKV07, AOSS08, GNT00, HdM15].
It often is unavoidable to draw a network without edge crossings. For example, the network of Figure 1 on Page 13 cannot be drawn with less than 144 crossings. One of the most important problems in this context is to find a drawing of the complete geometric graph on n vertices, Kn, (the network in which every two nodes are connected) with the least possible number of edge crossings. This minimum number of crossings is called the rectilinear crossing number of Kn. There is a huge amount of work on this topic, including many contributions from CONNECT members [ACFLS10, AFFFHSS11, AGOR07, AGOR09, FL14], with the currently best upper bound on the rectilinear crossing number obtained in [FL14]. A central topic of this project is the study of geometric networks in view of crossings of edges as a parameter. One of the simplest graph classes are perfect matchings. We propose to study the number of perfect matchings of point sets that have a given number k of crossings. Perfect matchings without crossings (k=0) have been studied. For point sets in convex position, the number of perfect matchings without edge crossings is given by the well-known Catalan numbers. So far, the case k>0 has been studied only for point sets in convex position.
We are interested in studying properties of networks that obey a certain geometric structure. Here, we aim to find a 'good' drawing of a network in order to derive properties of the network from that drawing. In particular, each drawing of a graph, satisfying some conditions, implies a bound on the algebraic connectivity or Fiedler value [F73] of the graph, denoted λ2. The Fiedler value has been used successfully for graph partitioning, separators, and is also related to the quality of geometric embeddings of the graph [ST96, ST07], in addition to having a special role in many problems in Physics and Chemistry. Several results have been obtained for λ2, see surveys [A07, M97]. As for recent works, the authors of [BLR10] make use of flows and the choice of an appropriate metric for proving bounds on λ2. In [BHMO13] two of the CONNECT members investigated the maximum possible value of λ2 for planar graphs, outerplanar graphs, and they gave bounds for graphs of bounded genus and Kh-minor-free graphs. We plan to investigate an integer version of λ2, building upon the work [JM96], which is related to bandwidth problems and has numerous applications (see [M91] for details).
Even though most progress in the study of geometric networks usually involves theoretical formulations, recently there have been some promising advancements due to the use of computing aid. We focus here on two relevant cases.
The order type [GP83] of a set of points in the plane is an abstraction of its combinatorial properties. While the number of possible positions of the nodes of a network is infinite, only a finite number of them have different order types. CONNECT member Dr. Aichholzer and coauthors [AAK02] managed to produce a database with all different order types up to 11 points. This database has had a large impact in Combinatorial Geometry; it has been used to verify or provide counter examples to conjectures, and to strengthen induction basis for proofs. The paper [AAK02] describing this database has over 90 citations according to Google Scholar. However, the order type does not capture all the geometric relationships of a point set. For example it does not determine its Delaunay triangulation nor its Gabriel graph.
One of the first applications of the order type database was in improving the upper bound on the rectilinear crossing number of the complete graph [AK07]. Various constructions have been developed for constructing arbitrarily large rectilinear drawings with few crossings of the complete graph, given a good starting “seed”' drawing. The best of these constructions so far has been given by CONNECT member Dr. Salazar and coauthors in [ACFLS10]. Dr. Aichholzer has compiled the best known drawings up to 100 vertices in his webpage. With a random heuristic, CONNECT member Dr. Fabila-Monroy and coauthor [FL14] improved the best known drawing for 75 points. This, combined with the construction of [ACFLS10], provides the best known upper bound on the rectilinear crossing number of the complete graph.
