Recognizing Partial Cubes in Quadratic Time - Eppstein, David (Journal of Graph Algorithms and Applications, 2011)
We show how to test whether a graph with n vertices and m edges is a partial cube, and if so how to find a distance-preserving embedding of the graph into a hypercube, in the near-optimal time bound O(n2), improving previous O(nm)-time solutions. <!---->