BARC talk by Deborah Haun

Tuesday, 27 May 2025, Deborah Haun, master's student at KIT in Germany, will give a talk on "Product Structure and Treewidth of Hyperbolic Uniform Disk Graphs".

Abstract:
A graph is a Euclidean/hyperbolic uniform disk graph (EUDG/HUDG) if its vertices can be represented by disks of equal radius in the Euclidean/hyperbolic plane such that two vertices are adjacent if and only if their disks intersect. It was recently proven that EUDGs admit product structure [Dvořák et al., 2021], i.e., each EUDG is a subgraph of the strong product of two paths and a complete graph. This formalizes their inherent grid-like structure.

Unlike for EUDGs, different radii allow us to embed different types of graphs in the hyperbolic plane. For example, very small radii enable us to embed grids similar to the Euclidean plane, while stars are only possible with a large radius. In this work, we use the notion of product structure to formally distinguish between the grid-like structure of small-radius HUDGs and the hierarchical structure of large-radius HUDGs.

Bio:
Deborah is a master's student at Karlsruhe Institute of Technology, Germany, where she also received her bachelor's degree. Her main research interests are graph structures and algorithms.

Host:
Tuukka Korhonen