The CONNECT is coming to an end. To commemorate this occasion a final conference will take place at Schloss Sankt Martin, from June 27th to July 1st 2022.

Monday 27th Tuesday 28th Wednesday 29th Thursday 30th Friday 1st
9:00 Open Problems Session Talk Session 3 Problem solving session and progress report Talk Session 5
10:00 Break Break
10:30 Talk Session 4 Problem solving Session
11:00 Break Break
11:30 Problem Solving Session Free Discussion Post-CONNECT: Identifying unsolved tasks of the project and planning future collaborative work
12:00 Progress Report and Closing
13:00 Lunch Lunch Lunch Lunch Lunch
14:00 Opening Session
14:30 Talk Session 1 Problem Solving Session Hike Problem Solving Session
15:30 Break
16:00 Talk Session 2 Break Break
16:30 Business and Final Report Meeting Problem Solving Session
17:00 Free Discussion
18:00 Dinner Dinner Dinner Dinner

Monday June 27th, Talk Sessions 1 and 2

  • 14:30-15:00 Birgit Vogtenhuber , Plane Structures in Simple Drawings of Complete Graphs
  • Plane structures in drawings of graphs are an active area of research. Among other things, they may be useful to prove structural or combinatorial results on the underlying graphs. For example, a lower bound on the number of combinatorially different simple drawings of the complete graph has been shown under the assumption that each such drawing contains a plane Hamiltonian cycle. However, it is still open whether this assumption holds as finding plane structures in those drawings turns out to be surprisingly difficult. In this talk, we discuss recent improvements on lower bounds for the number of pairwise disjoint edges and the length of plane paths in simple drawings of complete graphs. A main ingredient is a special class of simple drawings that we call generalized twisted drawings. These have surprising properties and might also be of interest for other questions.

  • 15:00-15:30 Carlos Seara, Rectilinear Convex Hull and Applications
  • In this talk we will show the latest results on the oriented and unoriented Rectilinear Convex Hull of a set of points in two and three dimensions, some applications of this concept and its relation with classical problems in Computational Geometry.

  • 16:00-16:30 Franz Lehner, Cyclic Boolean and Monotone Independence
  • The star product and comb product of finite graphs is simple enough to allow the explicit calculation spectra, Green's functions and various other parameters. The extension of these formulas to infinite dimensions leads to the abstract notions of cyclic Boolean and monotone independence.

  • 16:30-17:00 Fabian Klute, Fully Diverse Sets of Geometric Objects and Graphs
  • Diversity is a property of sets that shows how varied or different its elements are. We define full diversity in a metric space and study the maximum size of fully diverse sets. A set is fully diverse if each pair of elements is as distant as the maximum possible distance between any pair, up to a constant factor. We study metric spaces based on geometry,embeddings of graphs, and graphs themselves. In the geometric cases, we study measures like Hausdorff distance, Frechét distance, and area of symmetric difference between objects in a bounded region. In the embedding cases, we study planar embeddings of trees and planar graphs, and use the number of swaps in the rotation system as the metric. In the graph cases, we use the number of insertions and deletions of leaves or edges as the metric. In nearly all cases, we could recently show (almost) tight lower and upper bounds on the maximum size of fully diverse sets. During the talk I will give an introduction to our new definition of full diversity and discuss a selection of highlights from the set of our results. The focus will lie on both, the construction of fully diverse sets and the techniques used to show that this are indeed the best possible such sets. I will conclude with an overview of future directions and open problems.

  • 17:00-17:30 Pablo Perez [online], Maximum Matchings of Points
  • Given a set \(P \) of \(2n \) points in the plane, a matching of \(P\) is a partition \(\mathcal{M}=\{\{r_i,b_i\}\mid i=1,2,\ldots,n\}\) of the elements of \(P\), and we say that \(\mathcal{M}\) is maximum if it maximizes the sum \(\sum_{i=1}^n d(r_i,b_i)\) for a given distance function \(d\). In this talk we will summarize some new published results of our group regarding these matchings, and we will comment about our current work in this topic. The results include

    • If \(d\) is the Euclidean distance function, then all the disks induced by a maximum matching have a common intersection, where each matching pair \(\{r_i,b_i\}\) induces the disk having the segment \(r_ib_i\) as diameter.
    • If \(d\) is the squared Euclidean distance function, \(P=R\cup B\) is bichromatic with \(|R|=|B|=n\), and the maximum matching must be bichromatic (i.e. \(r_i\in R\) and \(b_i\in B\) for all \(i\)), then all the disks induced by a maximum matching have a common intersection.

Wednesday June 29th, Talk Session 3 and 4

  • 9:00-9:30 Cristina Dalfó, On the Laplacian Spectra of Token Graphs
  • The \(k\)-token graph \(F_k(G)\) of a graph \(G\) is the graph whose vertices are the \(k\)- subsets of vertices from \(G\), two of which are adjacent whenever their symmetric difference is a pair of adjacent vertices in \(G\). In this talk, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. Besides, we obtain a relationship between the spectra of the \(k\)-token graph of \(G\) and the \(k\)-token graph of its complement \(G\). This generalizes a well-known property for Laplacian eigenvalues of graphs to token graphs.

  • 9:30-10:00 José-Miguel Díaz-Bañez [online], Algorithms for Drones and Flamenco Music
  • We review the progress made in the Work Package 4 (Graph-based algorithms for UAVs and for MIR)

  • 10:30-11:00 Daniel Perz, Horton Set Manipulations
  • Horton sets were first introduced by Horton and were later described by Valtr. One property of them is, that they do not contain many empty triangles. We present in this talk how we used Horton sets as an underlying structures to construct point sets which do not contain many empty rainbow triangles. Further we construct point sets where no point of the plane is in a constant fraction of all empty triangles of the point set.

  • 11:30-12:00 Ruy Fabila, Crossing Numbers During the CONNECT Project
  • The crossing number of a graph \(G\) is the minimum of crossings that appear on every drawing of \(G\) in the plane. There are many variants such as when the edges are required to be drawn as straight line segments. In this talk we will give an overview of the problems studied and results obtained on crossing numbers during the CONNECT project.

Friday July 1st, Talk Session 5

  • 09:00-9:30 Bruce Richter, Straightening some drawings of graphs - extending theorems of Thomassen and of Bienstock and Dean
  • We prove a general straightening theorem for planar drawings of graphs. This gives easier proofs of Thomassen’s BW-theorem about drawings in which each edge is crossed at most once and the theorem of Bienstock and Dean that if \( \operatorname{cr}(G) \le 3 \), then the rectilinear crossing number of \(G\) is equal to its crossing number. Joint work with Alan Arroyo and Carsten Thomassen.

  • 9:30-10:00 Rosna Paul, Rotation systems and simple drawings in surfaces
  • It is easy to show that not every (abstract) rotation system can be realized by a simple drawing of a graph in the plane. As far as we know, Dan Archdeacon was the first to ask: which rotation systems can be realized by a simply drawing in the plane? In other words, which rotation systems can be simply realized in the plane? Kyncl answered this question, proving in particular that there is a polynomial-time algorithm that decides whether a given rotation system is simply realizable in the plane. Dan Archdeacon went further and considered this question for higher genus surfaces: given a compact surface $\Sigma$, which rotation systems can be simply realized in \(\Sigma\)? In this talk I will present some recent results related to this question. This is a joint work with Gelasio Salazar and Alexandra Weinberger.