Motivated by a dynamic location problem for graphs, Chung, Graham and Saks
introduced a graph parameter called winder. Graphs of winder 2 turned out t
o be, in graph-theoretic language, retracts of hypercubes. These graphs are
also known as median graphs and can be characterized as partial binary Ham
ming graphs satisfying a convexity condition. In this paper an O(n(3/2) log
n) algorithm is presented to recognize these graphs. As a by-product we ar
e also able to isometrically embed median graphs in hypercubes in O(m log n
) time. (C) 1999-Elsevier Science B.V. All rights reserved.