Imrich, Wilfried; Klavžar, Sandi A convexity lemma and expansion procedures for bipartite graphs. (English) Zbl 0918.05085 Eur. J. Comb. 19, No. 6, 677-685 (1998). 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. Reviewer: Jean Pallo (Dijon) Cited in 1 ReviewCited in 21 Documents MSC: 05C75 Structural characterization of families of graphs 05C85 Graph algorithms (graph-theoretic aspects) 68R10 Graph theory (including graph drawing) in computer science Keywords:recognition; bipartite graphs; Hamming graphs; median graphs; partial cubes; algorithms; complexity; expansion procedures; acyclic cubical complexes; convexity lemma PDFBibTeX XMLCite \textit{W. Imrich} and \textit{S. Klavžar}, Eur. J. Comb. 19, No. 6, 677--685 (1998; Zbl 0918.05085) Full Text: DOI Link