A convexity lemma and expansion procedures for bipartite graphs (Q1272768)

Consider the hierarchy \(\text{H}\subset\text{M} \subset\text{PC}\) where H is the class of Hamming graphs, M the class of median graphs and PC the class of partial cubes. The best-known algorithms for recognizing whether a graph \(G\) is a member of the classes H, M and PC have respectively time complexity \(O(m)\), \(O(mn^{1/2})\) and \(O(mn)\) where \(m\) (resp. \(n\)) denotes the number of edges (resp. vertices) of \(G\). Using expansion procedures, the authors introduce the class AM of almost-median graphs and the class PM of semi-medians graphs. If we add the class ACC of so-called acyclic cubical complexes introduced recently, we obtain the following hierarchy: \(\text{H}\subset \text{ACC} \subset\text{M} \subset\text{AM}\subset \text{PM} \subset\text{PC}\). The authors begin with a convexity lemma which they then use to exhibit a new algorithm of complexity \(O(mn)\) for recognizing median graphs. The class PM is characterized and a new characterization of M by forbidden subgraphs is given.