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(n^2), improving previous O(nm)-time solutions.
@cite_36: 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 lattice Zd.
Every partial cube may be embedded in a distance-preserving way into an integer lattice @math of some dimension @math . One such labeling simply uses each bit of a bitvector labeling as a coordinate in @math ; however, some graphs may be embeddable into integer lattices of much lower dimension than their isometric dimension. For instance, a path graph can be embedded into @math , and given one-dimensional coordinates that accurately describe the graph distances, despite having an isometric dimension of @math . The of a partial cube is the minimum number @math for which the graph admits a distance-preserving embedding into @math . The lattice dimension, and an embedding of that dimension, may be found in polynomial time using an algorithm based on graph matching @cite_36 , but this algorithm depends on having as input a bitvector labeling and is slower than the algorithm we describe here, so it does not form the basis of an efficient partial cube recognition algorithm.