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.