Invited Speakers

Walter Didimo - University of Perugia, Italy

Orthogonal Graph Drawings and the Bend Minimization Problem

Orthogonal drawings have a rich history and rank among the most extensively studied subjects in graph drawing. They have wide-ranging applications in several real-world domains, including circuit design, computer network schematization, database design, and software engineering. In an orthogonal drawing of a graph, each edge is a sequence of horizontal and vertical segments, with a bend being the point where a horizontal segment and a vertical segment intersect. Since bends can adversely impact the readability of the graph layout, a central problem is how to compute orthogonal drawings with the minimum number of bends.

Following a brief overview on the subject, this talk focuses on a line of research that leverages the notion of "spirality", a measure of how much a component of an orthogonal drawing is rolled-up. A general strategy based on this notion was introduced over 25 years ago. This strategy has been recently revisited and refined to answer long-standing open questions, also in the presence of specific layout constraints.

Ioannis Emiris - Athena Research Center, National & Kapodistrian University of Athens, Greece

Algebraic and combinatorial bounds on the embedding number of distance graphs

Rigidity theory studies mechanisms with a prescribed number of degrees of freedom. Besides its fundamental nature, the theory is particularly useful in modeling robotic and architectural devices, swarms of drones or the structure of biomolecules. The main tool is distance graphs, whose study becomes a centerpiece of such studies. Laman graphs are the most well-known, but distance graphs can be defined and find applications in any dimension. We focus on estimating the number of Euclidean embeddings of these graphs, which is today a very active domain of research, and present recent progress in this field. Namely, we exploit algebraic and combinatorial techniques to obtain nontrivial upper bounds on the maximal number of embeddings. Conversely, we consider ways of deriving relevant root counts for polynomial systems expressed by means of distance graphs.

Xavier Goaoc (Université de Lorraine, Nancy, France)

Intersection patterns of geometric set systems

In this talk, I will discuss some of the ways in which the geometry or topology of a family of sets influence their intersection patterns, and illustrate how the resulting structures are harnessed by some algorithms from computational geometry and computational topology.

Gold sponsors

Contributors