Recognizing halved cubes in a constant time per edge

Graphs that can be isometrically embedded into the metric space l1 are called l1-graphs. Halved cubes play an important role in the characterization of l1-graphs. We present an algorithm that recognizes halved cubes in O(n log2 n) time.