Fast recognition algorithms for classes of partial cubes

Isometric subgraphs of hypercubes, or partial cubes as they are also called, are a rich class of graphs that include median graphs, subdivision graphs of complete graphs, and classes of graphs arising in mathematical chemistry and biology. In general, one can recognize whether a graph on <f>n</f> vertices and <f>m</f> edges is a partial cube in <f>O(mn)</f> steps, faster recognition algorithms are only known for median graphs. This paper exhibits classes of partial cubes that are not median graphs but can be recognized in <f>O(m log n)</f> steps. On the way relevant decomposition theorems for partial cubes are derived, one of them correcting an error in a previous paper (Eur. J. Combin. 19 (1998) 677). [Copyright &y& Elsevier]