32 citations · 32 across the 10 of their papers we have counts for
10 papers
Minimum-Weight Steiner Triangulation of Convex Polygons Requires Interior Steiner Points
David Eppstein, Zahra Hadizadeh
We construct a convex polygon for which the minimum-weight Steiner triangulation requires an interior Steiner point. This provides a counterexample to a 1994 conjecture of Eppstein…
Tangent Spheres and Integer Distances
David Eppstein
The Erdős-Anning theorem states that any point set for which all distances are integers, in a Euclidean space of any dimension, must be either finite or collinear. We prove the sam…
Hamiltonian Cycles in Subdivided Doubles
David Eppstein
The subdivided double construction on 4-regular graphs was used by Potočnik and Wilson to explore semi-symmetric (edge-transitive but not vertex-transitive) graphs, and can be used…
String Graph Obstacles of High Girth and of Bounded Degree
Maria Chudnovsky, David Eppstein, David Fischer
A string graph is the intersection graph of curves in the plane. Kratochvíl previously showed the existence of infinitely many obstacles: graphs that are not string graphs but for…
Entropy-Bounded Computational Geometry Made Easier and Sensitive to Sortedness
David Eppstein, Michael T. Goodrich, Abraham M. Illickan +1
We study entropy-bounded computational geometry, that is, geometric algorithms whose running times depend on a given measure of the input entropy. Specifically, we introduce a meas…
Visualizing Treewidth
Alvin Chiu, Thomas Depian, David Eppstein +2
A witness drawing of a graph is a visualization that clearly shows a given property of a graph. We study and implement various drawing paradigms for witness drawings to clearly sho…
Better Late than Never: the Complexity of Arrangements of Polyhedra
Boris Aronov, Sang Won Bae, Sergio Cabello +4
Let be the subdivision of induced by convex polyhedra having facets in total. We prove that has combinatorial complexity $O(m^{\l…
Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing
David Eppstein, Michael T. Goodrich, Songyu Liu
We provide the first approximation quality guarantees for the Cuthull-McKee heuristic for reordering symmetric matrices to have low bandwidth, and we provide an algorithm for recon…
Drawing Planar Graphs and 1-Planar Graphs Using Cubic Bézier Curves with Bounded Curvature
David Eppstein, Michael T. Goodrich, Abraham M. Illickan
We study algorithms for drawing planar graphs and 1-planar graphs using cubic Bézier curves with bounded curvature. We show that any n-vertex 1-planar graph has a 1-planar RAC draw…
Combinatorics and geometry of finite and infinite squaregraphs
Hans-Jurgen Bandelt, Victor Chepoi, David Eppstein
Squaregraphs were originally defined as finite plane graphs in which all inner faces are quadrilaterals (i.e., 4-cycles) and all inner vertices (i.e., the vertices not incident wit…