2005
Note that a paper may appear in listings for multiple years due to multiple publication (of tech. report, conference, and journal versions).- Hinged dissections of polyominos and polyforms.
E. Demaine, M. Demaine, D. Eppstein, G. Frederickson, and E. Friedman.
arXiv:cs.CG/9907018.
11th Canad. Conf. Comp. Geom., 1999.
Computational Geometry: Theory and Applications 31 (3): 237–262, 2005 (special issue for 11th CCCG).We show that, for any n, there exists a mechanism formed by connecting polygons with hinges that can be folded into all possible n-ominos. Similar results hold as well for n-iamonds, n-hexes, and n-abolos.
- 3-coloring in time O(1.3289^n).
R. Beigel and D. Eppstein.
arXiv:cs.DS/0006046.
J. Algorithms 54:2 (2005) 168-204.Journal paper combining 3-coloring algorithms from our FOCS '95 paper with improved bounds from our SODA '01 paper.
- Reference caching using unit distance redundant codes for
activity reduction on address buses.
D. Eppstein and T. Givargis.
Worksh. Embedded System Codesign (ESCODES'02), San Jose, 2002, pp. 43–48.
J. Microprocessors & Microsystems 29 (4): 145–153, 2005.We study the problem of minimizing transitions in address signals on a bus. The UDRC part of the title refers to an algorithm for coding signals with at most one transition per signal (using an increased number of wires); we combine this with a scheme for caching previously coded addresses and use trace data to compare our technique with previous approaches.
- Confluent drawings: visualizing non-planar diagrams in a planar way.
M. Dickerson, D. Eppstein, M. T. Goodrich, and J. Meng.
arXiv:cs.CG/0212046.
11th Int. Symp. Graph Drawing, Perugia, Italy, 2003.
Springer, Lecture Notes in Comp. Sci. 2912, 2004, pp. 1–12.
J. Graph Algorithms and Applications (special issue for GD'03) 9 (1): 31–52, 2005.We describe a new method of drawing graphs, based on allowing the edges to be merged together and drawn as "tracks" (similar to train tracks). We present heuristics for finding such drawings based on my previous algorithms for finding maximal bipartite subgraphs, prove that several important families of graphs have confluent drawings, and provide examples of other graphs that can not be drawn in this way.
- Quasiconvex programming.
D. Eppstein.
Invited talk at DIMACS Worksh. on Geometric Optimization, New Brunswick, NJ, 2003.
Plenary talk at ALGO 2004, Bergen, Norway, 2004.
arXiv:cs.CG/0412046.
Combinatorial and Computational Geometry, Goodman, Pach, and Welzl, eds., MSRI Publications 52, 2005, pp. 287–331.Defines quasiconvex programming, a form of generalized linear programming in which one seeks the point minimizing the pointwise maximum of a collection of quasiconvex functions. Surveys algorithms for solving quasiconvex programs either numerically or via generalizations of the dual simplex method from linear programming, and describe varied applications of this geometric optimization technique in meshing, scientific computation, information visualization, automated algorithm analysis, and robust statistics.
- The lattice dimension of a graph.
D. Eppstein.
arXiv:cs.DS/0402028.
Eur. J. Combinatorics 26 (6): 585–592, 2005.Describes a polynomial time algorithm for isometrically embedding graphs into an integer lattice of the smallest possible dimension. The technique involves maximum matching in an auxiliary graph derived from a partial cube representation of the input.
- Confluent layered drawings.
D. Eppstein, M. T. Goodrich, and J. Meng.
12th Int. Symp. Graph Drawing, New York, 2004.
Springer, Lecture Notes in Comp. Sci. 3383, 2004, pp. 184–194.
arXiv:cs.CG/0507051.
Algorithmica 47 (4): 439–452 (special issue for Graph Drawing), 2007.Describes a graph drawing technique combining ideas of confluent drawing with Sugiyama-style layered drawing. Uses a reduction to graph coloring to find and visualize sets of bicliques in each layer.
- All maximal independent sets and dynamic dominance for sparse
graphs.
D. Eppstein.
arXiv:cs.DS/0407036.
16th ACM-SIAM Symp. Discrete Algorithms, Vancouver, 2005, pp. 451–459.
ACM Trans. Algorithms 5(4):A38, 2009.We show how to apply reverse search to list all maximal independent sets in bounded-degree graphs in constant time per set, in graphs from minor closed families in linear time per set, and in sparse graphs in subquadratic time per set. The latter two results rely on new data structures for maintaining a dynamic vertex set in a graph and quickly testing whether the set dominates all other vertices.
- Minimum dilation stars.
D. Eppstein and K. Wortman.
arXiv:cs.CG/0412025.
21st ACM Symp. Comp. Geom., Pisa, 2005, pp. 321–326.
Comp. Geom. Theory & Applications 37 (1): 27–37, 2007.We show how to test the dilation of a star, embedded in a Euclidean space of bounded dimension, in time O(n log n), and how to find the star center that has the minimum dilation for a given set of leaf points in randomized expected time O(n log n). For two-dimensional points, we can find the minimum dilation center, constrained to be one of the input points, in time O(n 2α(n) log2n). The unconstrained center placement algorithm involves quasiconvex programming, and is used as a subroutine in the constrained center placement algorithm.
- Improved combinatorial group testing for
real-world problem sizes.
D. Eppstein, M. T. Goodrich, and D. S. Hirschberg.
9th Worksh. Algorithms and Data Structures, Waterloo, 2005.
Springer, Lecture Notes in Comp. Sci. 3608, 2005, pp. 86–98.
arXiv:cs.DS/0505048.
SIAM J. Computing 36 (5): 1360–1375, 2007.We study practically efficient methods for finding few flawed items among large sets of items, by testing whether there exist flaws in each of a small number of batches of items.
- The skip quadtree: a simple dynamic data structure
for multidimensional data.
D. Eppstein, M. T. Goodrich, and J. Z. Sun.
21st ACM Symp. Comp. Geom., Pisa, 2005, pp. 296–305.
arXiv:cs.CG/0507049.
Int. J. Comp. Geom. & Appl. 18(1-2): 131–160, 2008.We describe a data structure consisting of a sequence of compressed quadtrees for successively sparser samples of an input point set, with connections between the same squares in successive members of the sequence. Using this structure, we can insert or delete points and answer approximate range queries and approximate nearest neighbor queries in O(log n) time per operation.
- Skip-webs: efficient distributed data structures for
multi-dimensional data sets.
L. Arge, D. Eppstein, and M. T. Goodrich.
Proc. 24th ACM SIGACT-SIGOPS Symp. Principles of Distributed Computing (PODC 2005), Las Vegas, July 2005, pp. 69–76.
arXiv:cs.DC/0507050.Describes efficient distributed versions of skip quadtrees and related spatial searching structures.
- The weighted maximum-mean subtree and other bicriterion subtree problems.
J. Carlson and D. Eppstein.
arXiv:cs.CG/0503023.
Proc. 10th Scand. Worksh. Algorithm Theory (SWAT 2006).
Springer, Lecture Notes in Comp. Sci. 4059, 2006, pp. 397–408.We give a linear time algorithm for pruning a node-weighted tree to maximize the average node weight of the pruned subtree; this problem was previously studied under the less obvious name "The Fractional Prize-Collecting Steiner Tree Problem on Trees".
- Delta-confluent drawings.
D. Eppstein, M. T. Goodrich, and J. Meng.
13th Int. Symp. Graph Drawing, Limerick, Ireland, 2005.
Springer, Lecture Notes in Comp. Sci. 3843, 2006, pp. 165–176.
arXiv:cs.CG/0510024.
We characterize the graphs that can be drawn confluently with a single confluent track that is tree-like except for three-way Delta junctions, as being exactly the distance hereditary graphs. Based on this characterization, we develop efficient algorithms for drawing these graphs.
- Nonrepetitive paths and cycles in graphs with application to Sudoku.
D. Eppstein.
arXiv:cs.DS/0507053.We describe algorithms and hardness results for finding paths in edge-labeled graphs such that no two consecutive edges have the same label, and use our algorithms to implement heuristics for a program that automatically solves and generates Sudoku puzzles.
- Cubic partial cubes from simplicial arrangements.
D. Eppstein.
arXiv:math.CO/0510263.
Electronic J. Combinatorics 13(1), Paper R79, 2006.We show how to construct a cubic partial cube from any simplicial arrangement of lines or pseudolines in the projective plane. As a consequence, we find nine new infinite families of cubic partial cubes as well as many sporadic examples.
- Single triangle strip and loop on manifolds with boundaries.
A. Bushan, P. Diaz-Gutierrez, D. Eppstein, and M. Gopi.
Tech. Rep. 05-11, UC Irvine, School of Information and Computer Science, 2005.
Proc. 19th Brazilian Symp. Computer Graphics and Image Processing (SIBGRAPI 2006), pp. 221–228.This follows on to our previous paper on using graph matching to cover a triangulated polyhedral model with a single triangle strip by extending the algorithms to models with boundaries. We provide two methods: one is based on using an algorithm for the Chinese Postman problem to find a small set of triangles to split in order to find a perfect matching in the dual mesh, while the other augments the model with virtual triangles to remove the boundaries and merges the strips formed by our previous algorithm on this augmented model. We implement the algorithms and report some preliminary experimental results.