72 citations · 218 across the 15 of their papers we have counts for
8 papers · 1 filter
Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku
David Eppstein
We provide a simple linear time transformation from a directed or undirected graph with labeled edges to an unlabeled digraph, such that paths in the input graph in which no two co…
Algorithms for Drawing Media
David Eppstein
We describe algorithms for drawing media, systems of states, tokens and actions that have state transition graphs in the form of partial cubes. Our algorithms are based on two prin…
The lattice dimension of a graph
David Eppstein
We describe a polynomial time algorithm for, given an undirected graph G, finding the minimum dimension d such that G may be isometrically embedded into the d-dimensional integer l…
Quasiconvex Analysis of Backtracking Algorithms
David Eppstein
We consider a class of multivariate recurrences frequently arising in the worst case analysis of Davis-Putnam-style exponential time backtracking algorithms for NP-hard problems. W…
Dynamic Generators of Topologically Embedded Graphs
David Eppstein
We provide a data structure for maintaining an embedding of a graph on a surface (represented combinatorially by a permutation of edges around each vertex) and computing generators…
Algorithms for Media
David Eppstein, Jean-Claude Falmagne
Falmagne recently introduced the concept of a medium, a combinatorial object encompassing hyperplane arrangements, topological orderings, acyclic orientations, and many other famil…