Marcus Schaefer
YOU?
Author Swipe
View article: RAC-Drawability is ∃ℝ-complete and Related Results
RAC-Drawability is ∃ℝ-complete and Related Results Open
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 existential theory of the reals, even if we know that every edge…
View article: The Complexity of Angular Resolution
The Complexity of Angular Resolution Open
The angular resolution of a straight-line drawing of a graph is the smallest angle formed by any two edges incident to a vertex. The angular resolution of a graph is the supremum of the angular resolutions of all straight-line drawings of …
View article: Hanani-Tutte for Radial Planarity II
Hanani-Tutte for Radial Planarity II Open
A drawing of a graph $G$, possibly with multiple edges but without loops, is radial if all edges are drawn radially, that is, each edge intersects every circle centered at the origin at most once. $G$ is radial planar if it has a radial em…
View article: Beyond the Existential Theory of the Reals
Beyond the Existential Theory of the Reals Open
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 recognized gaps in the hierarchy, and leads to stronger complete…
View article: Spiraling and Folding: The Topological View
Spiraling and Folding: The Topological View Open
For every $n$, we construct two curves in the plane that intersect at least $n$ times and do not form spirals. The construction is in three stages: we first exhibit closed curves on the torus that do not form double spirals, then arcs on t…
View article: The Degenerate Crossing Number and Higher-Genus Embeddings
The Degenerate Crossing Number and Higher-Genus Embeddings Open
If a graph embeds in a surface with $k$ crosscaps, does it always have an embedding in the same surface in which every edge passes through each crosscap at most once? This well-known open problem can be restated using crossing numbers: the…
View article: A New Algorithm for Embedding Plane Graphs at Fixed Vertex Locations
A New Algorithm for Embedding Plane Graphs at Fixed Vertex Locations Open
We show that a plane graph can be embedded with its vertices at arbitrarily assigned locations in the plane and at most $6n-1$ bends per edge. This improves and simplifies a classic result by Pach and Wenger. The proof extends to orthogona…
View article: RAC-drawability is ∃R-complete.
RAC-drawability is ∃R-complete. Open
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 existential theory of the reals, even if we know that every edge…
View article: RAC-drawability is $\exists\mathbb{R}$-complete
RAC-drawability is $\exists\mathbb{R}$-complete Open
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 existential theory of the reals, even if we know that every edge…
View article: Complexity of Geometric k-Planarity for Fixed k
Complexity of Geometric k-Planarity for Fixed k Open
The rectilinear local crossing number, $\mathop{\overline{\rm lcr}}(G)$, of a graph $G$ is the smallest $k$ so that $G$ has a straight-line drawing with at most $k$ crossings along each edge. We show that deciding whether $\mathop{\overlin…
View article: Strong Hanani-Tutte for the Torus
Strong Hanani-Tutte for the Torus Open
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.
View article: On the Complexity of Some Geometric Problems With Fixed Parameters
On the Complexity of Some Geometric Problems With Fixed Parameters Open
The following graph-drawing problems are known to be complete for the existential theory of the reals (${\exists \mathbb{R}}$-complete) as long as the parameter $k$ is unbounded. Do they remain ${\exists \mathbb{R}}$-complete for a fixed v…
View article: Strong Hanani-Tutte for the Torus
Strong Hanani-Tutte for the Torus Open
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.
View article: Link crossing number is NP-hard
Link crossing number is NP-hard Open
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.
View article: A Proof of Levi's Extension Lemma
A Proof of Levi's Extension Lemma Open
We give a short and self-contained proof of Levi's Extension Lemma for pseudoline arrangements.
View article: A Note on the Maximum Rectilinear Crossing Number of Spiders
A Note on the Maximum Rectilinear Crossing Number of Spiders Open
The maximum rectilinear crossing number of a graph $G$ is the maximum number of crossings in a good straight-line drawing of $G$ in the plane. In a good drawing any two edges intersect in at most one point (counting endpoints), no three ed…
View article: Hanani-Tutte for Radial Planarity
Hanani-Tutte for Radial Planarity Open
A drawing of a graph $G$ is radial if the vertices of $G$ are placed on concentric circles $C_1, \ldots, C_k$ with common center $c$, and edges are drawn radially: every edge intersects every circle centered at $c$ at most once. $G$ is rad…
View article: The Complexity of Tensor Rank
The Complexity of Tensor Rank Open
We show that determining the rank of a tensor over a field has the same complexity as deciding the existential theory of that field. This implies earlier NP-hardness results by Håstad~\cite{H90}. The hardness proof also implies an algebrai…
View article: Hanani-Tutte for Radial Planarity II
Hanani-Tutte for Radial Planarity II Open
A drawing of a graph $G$ is radial if the vertices of $G$ are placed on concentric circles $C_1, \ldots, C_k$ with common center $c$, and edges are drawn radially: every edge intersects every circle centered at $c$ at most once. $G$ is rad…
View article: Drawing Partially Embedded and Simultaneously Planar Graphs
Drawing Partially Embedded and Simultaneously Planar Graphs Open
We investigate the problem of constructing planar drawings with few bends for two related problems, the partially embedded graph problem-to extend a straight-line planar drawing of a subgraph to a planar drawing of the whole graph-and the …