321 citations · 2k across the 200 of their papers we have counts for
13 papers · 1 filter
From Discrepancy to Majority
David Eppstein, Daniel S. Hirschberg
We show how to select an item with the majority color from two-colored items, given access to the items only through an oracle that returns the discrepancy of subsets of it…
On the Planar Split Thickness of Graphs
David Eppstein, Philipp Kindermann, Stephen Kobourov +7
Motivated by applications in graph drawing and information visualization, we examine the planar split thickness of a graph, that is, the smallest such that the graph is -spl…
Treetopes and their Graphs
David Eppstein
We define treetopes, a generalization of the three-dimensional roofless polyhedra (Halin graphs) to arbitrary dimensions. Like roofless polyhedra, treetopes have a designated base…
Confluent Orthogonal Drawings of Syntax Diagrams
Michael J. Bannister, David A. Brown, David Eppstein
We provide a pipeline for generating syntax diagrams (also called railroad diagrams) from context free grammars. Syntax diagrams are a graphical representation of a context free la…
Rigid Origami Vertices: Conditions and Forcing Sets
Zachary Abel, Jason Cantarella, Erik D. Demaine +5
We develop an intrinsic necessary and sufficient condition for single-vertex origami crease patterns to be able to fold rigidly. We classify such patterns in the case where the cre…
Approximate Greedy Clustering and Distance Selection for Graph Metrics
David Eppstein, Sariel Har-Peled, Anastasios Sidiropoulos
In this paper, we consider two important problems defined on finite metric spaces, and provide efficient new algorithms and approximation schemes f…