2 papers
cs.CG2025
Recognizing Penny and Marble Graphs is Hard for Existential Theory of the Reals
Anna Lubiw, Marcus Schaefer
We show that the recognition problem for penny graphs (contact graphs of unit disks in the plane) is -complete, that is, computationally as hard as the existenti…
cs.CG2025
Finding a Shortest Curve that Separates Few Objects from Many
Therese Biedl, Éric Colin de Verdière, Fabrizio Frati +2
We present a fixed-parameter tractable (FPT) algorithm to find a shortest curve that separates some polygons from others. Formally, the input is a set of interior-disjoint simple p…