5 papers
Layer-Respecting Linear Graph Layouts
Alvin Chiu, David Eppstein, Michael T. Goodrich +1
We show how to visualize a graph, , as a layered drawing, layer-respecting arc diagram, or layer-respecting linear cylindric drawing with a minimum number of edge crossing…
Sudoku Grids That Require Many Clues
David Eppstein, Xinyu, Zhang
Motivated by worst-case algorithmic time bounds for solving sudoku, we prove that a majority of filled-in sudoku grids require all but a logarithmic fraction of cel…
On the expansion of Hanoi graphs
David Eppstein, Daniel Frishberg, William Maxwell
The famous Tower of Hanoi puzzle involves moving discs of distinct sizes from one of pegs (traditionally ) to another of the pegs, subject to the constraints tha…
Computational Geometry with Probabilistically Noisy Primitive Operations
David Eppstein, Michael T. Goodrich, Vinesh Sridhar
Much prior work has been done on designing computational geometry algorithms that handle input degeneracies, data imprecision, and arithmetic round-off errors. We take a new approa…
Zip-Tries: Simple Dynamic Data Structures for Strings
David Eppstein, Ofek Gila, Michael T. Goodrich +1
In this paper, we introduce zip-tries, which are simple, dynamic, memory-efficient data structures for strings. Zip-tries support search and update operations for -length string…