20 citations · 31 across the 10 of their papers we have counts for
12 papers
Beyond the Existential Theory of the Reals
Marcus Schaefer, Daniel Stefankovic
We show that completeness at higher levels of the theory of the reals is a robust notion (under changing the signature and bounding the domain of the quantifiers). This mends recog…
Spiraling and Folding: The Topological View
Jan Kynčl, Marcus Schaefer, Eric Sedgwick +1
For every , we construct two curves in the plane that intersect at least times and do not form spirals. The construction is in three stages: we first exhibit closed curves o…
RAC-drawability is -complete
Marcus Schaefer
A RAC-drawing of a graph is a straight-line drawing in which every crossing occurs at a right-angle. We show that deciding whether a graph has a RAC-drawing is as hard as the exist…
Strong Hanani-Tutte for the Torus
Radoslav Fulek, Michael J. Pelsmajer, Marcus Schaefer
If a graph can be drawn on the torus so that every two independent edges cross an even number of times, then the graph can be embedded on the torus.
A Proof of Levi's Extension Lemma
Marcus Schaefer
We give a short and self-contained proof of Levi's Extension Lemma for pseudoline arrangements.
Link Crossing Number is NP-hard
Arnaud de Mesmay, Marcus Schaefer, Eric Sedgwick
We show that determining the crossing number of a link is NP-hard. For some weaker notions of link equivalence, we also show NP-completeness.