Recognition of the \(\ell_ 1\)-graphs with complexity \(O(nm)\), or Football in a hypercube (Q1911847)

Adapted from the authors' introduction: We fill in the details of the algorithm sketched in the second author's paper [On scale embeddings of graphs into hypercubes, Eur. J. Comb. 14, No. 2, 117-130 (1993; Zbl 0773.05044)], and determine its complexity. As part of this main algorithm, we also describe an algorithm which recognizes graphs which are isometric subgraphs of halved cubes. We discuss possible further applications of the same ideas and give a nice example of a non-\(\ell_1\)-graph allowing a highly isometric embedding into a halved cube.