Recognizing halved cubes in a constant time per edge (Q1902967)

Graphs that can be isometrically embedded into the metric space \(l_1\) are called \(l_1\)-graphs. It has been proved that a graph is an \(l_1\)-graph iff it is an isometric subgraph of a Cartesian product of complete graphs, cocktail graphs or halved cubes. This paper presents an algorithm that recognizes halved cubes in \(O(n\log^2 n)\) time. The proposed algorithm is based on Hemmeter's observations on the properties of cliques in a halved cube. It remains still open whether we can decide in \(O(mn)\) time if a graph is an isometric subgraph of a halved cube.