David Eppstein - Publications

Publications with Sergei Ovchinnikov

• Media Theory: Interdisciplinary Applied Mathematics.
  D. Eppstein, J.-C. Falmagne, and S. Ovchinnikov.
  Springer, 2007, ISBN 978-3-540-71696-9.

  Many combinatorial structures such as the set of acyclic orientations of a graph, weak orderings of a set of elements, or chambers of a hyperplane arrangement have the structure of a partial cube, a graph in which vertices may be labeled by bitvectors in such a way that graph distance equals Hamming distance. This book analyzes these structures in terms of operations that change one vertex to another by flipping a single bit of the bitvector labelings. It incorporates material from several of my papers including "Algorithms for Media", "Algorithms for Drawing Media", "Upright-Quad Drawing of st-Planar Learning Spaces", and "The Lattice Dimension of a Graph".

  (Publisher's web site – Reinhard Suck's review in J. Math. Psych. – Reinhard Suck's review in MathSciNet)