Recognizing median graphs in subquadratic time

Motivated by a dynamic location problem for graphs, Chung, Graham and Saks introduced a graph parameter called windex. Graphs of windex 2 turned out to be, in graph-theoretic language, retracts of hypercubes. These graphs are also known as median graphs and can be characterized as partial binary Hamming graphs satisfying a convexity condition. In this paper an O(n3/2 log n) algorithm is presented to recognize these graphs. As a by-product we are also able to isometrically embed median graphs in hypercubes in O(m log n) time.