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 encloses a set of k required objects in the plane while paying a penalty for enclosing unwanted…