5 papers · 1 filter
Light Euclidean Steiner Spanners in the Plane
Sujoy Bhore, Csaba D. Tóth
Lightness is a fundamental parameter for Euclidean spanners; it is the ratio of the spanner weight to the weight of the minimum spanning tree of a finite set of points in $\mathbb{…
Reconfiguration of Connected Graph Partitions via Recombination
Hugo A. Akitaya, Matias Korman, Oliver Korten +2
Motivated by applications in gerrymandering detection, we study a reconfiguration problem on connected partitions of a connected graph . A partition of is \emph{connected…
Simple Topological Drawings of -Planar Graphs
Michael Hoffmann, Chih-Hung Liu, Meghana M. Reddy +1
Every finite graph admits a \emph{simple (topological) drawing}, that is, a drawing where every pair of edges intersects in at most one point. However, in combination with other re…
Universal Geometric Graphs
Fabrizio Frati, Michael Hoffmann, Csaba D. Tóth
We introduce and study the problem of constructing geometric graphs that have few vertices and edges and that are universal for planar graphs or for some sub-class of planar graphs…
Sparse Hop Spanners for Unit Disk Graphs
Adrian Dumitrescu, Anirban Ghosh, Csaba D. Tóth
A unit disk graph on a given set of points in the plane is a geometric graph where an edge exists between two points if and only if . A spanning su…