Recognizing median graphs in subquadratic time

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.