David Eppstein - Publications

Graph coloring

• 3-Coloring in time O(1.3446ⁿ): a no-MIS algorithm.
  R. Beigel and D. Eppstein.
  Tech. Rep. 95-033, Electronic Coll. Computational Complexity, 1995.
  36th IEEE Symp. Foundations of Comp. Sci., 1995, pp. 444–453.
  DIMACS Worksh. Faster Exact Solutions for NP-Hard Problems, 2000.

  Speeds up 3-coloring by solving a harder problem: constraint satisfaction in which each variable can take on one of three values and each constraint forbids a pair of variable assignments. The detailed solution involves several long hairy case analyses. Similar methods apply also to 3-list-coloring, 3-edge-coloring, and 3-SAT. The 3-SAT algorithm is fixed-parameter tractible in that it is polynomial time when the number of 3-variable clauses is O(log n). Merged into 3-coloring in time O(1.3289^n) for the journal version.

  (DIMACS abstract and slides)

• Algorithms for coloring quadtrees.
  M. Bern, D. Eppstein, and B. Hutchings.
  arXiv:cs.CG/9907030.
  Algorithmica 32 (1): 87–94, 2002.

  We consider several variations of the problem of coloring the squares of a quadtree so that no two adjacent squares are colored alike. We give simple linear time algorithms for 3-coloring balanced quadtrees with edge adjacency, 4-coloring unbalanced quadtrees with edge adjacency, and 6-coloring balanced or unbalanced quadtrees with corner adjacency. The number of colors used by the first two algorithms is optimal; for the third algorithm, 5 colors may sometimes be needed.

• 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.

• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
  D. Eppstein.
  arXiv:cs.DS/0009006.
  12th ACM-SIAM Symp. Discrete Algorithms, Washington, 2001, pp. 329–337.

  Summarizes recent improvements to "3-Coloring in time O(1.3446ⁿ): a no-MIS algorithm". Merged with that paper for the journal version.

  (SODA talk slides – SODA paper)

• Small maximal independent sets and faster exact graph coloring.
  D. Eppstein.
  arXiv:cs.DS/0011009.
  7th Worksh. Algorithms and Data Structures, Providence, Rhode Island, 2001.
  Springer, Lecture Notes in Comp. Sci. 2125, 2001, pp. 462–470.
  J. Graph Algorithms and Applications (special issue for WADS'01) 7 (2): 131–140, 2003.

  We show that any graph can be colored in time O(2.415ⁿ), by a dynamic programming procedure in which we extend partial colorings on subsets of the vertices by adding one more color for a maximal independent set. The time bound follows from limiting our attention to maximal independent subsets that are small relative to the previously colored subset, and from bounding the number of small maximal independent subsets that can occur in any graph.

  (WADS talk slides)

• 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.

• Choosing colors for geometric graphs via color space embeddings.
  M. Dillencourt, D. Eppstein, and M. T. Goodrich.
  arXiv:cs.CG/0609033.
  14th Int. Symp. Graph Drawing, Karlsruhe, Germany, 2006.
  Springer, Lecture Notes in Comp. Sci. 4372, 2007, pp. 294–305.

  We show how to choose colors for the vertices of a graph drawing in such a way that all colors are easily distinguishable, but such that adjacent vertices have especially dissimilar colors, by considering the problem as one of embedding the graph into a three-dimensional color space.

  (GD'06 talk slides)

• Minimum forcing sets for Miura folding patterns.
  B. Ballinger, M. Damian, D. Eppstein, R. Flatland, J. Ginepro, and T. Hull.
  arXiv:1410.2231.
  26th ACM-SIAM Symp. on Discrete Algorithms, San Diego, 2015, pp. 136–147.

  A forcing set for an origami crease pattern is a subset of the folds with the property that, if these folds are folded the correct way (mountain vs valley) the rest of the pattern also has to be folded the correct way. We use a combinatorial equivalence with three-colored grids to construct minimum-cardinality forcing sets for the Miura-ori folding pattern and for other patterns with differing folds along the same line segments.

  (Slides)