Convex-Expansions Algorithms for Recognition and Isometric Embedding of Median Graphs

Let \(G = (V, E)\) be a finite, simple graph. For a triple of vertices \(u, v, w\) of \(G\), a vertex \(x\) of \(G\) is a median of \(u, v\), and \(w\) if \(x\) lies simultaneously on shortest paths joining \(u\) and \(v\), \(v\) and \(w\), and \(w\) and \(u\) respectively. \(G\) is a median graph if \(G\) is connected, and every triple of vertices of \(G\) admits a unique median. There are several characterizations of median graphs in the literature; one given by Mulder is as follows: \(G\) is a median graph if and only if \(G\) can be obtained from a one-vertex graph by a sequence of convex expansions. We present an \(O(|V|^2 \log |V|)\) algorithm for recognizing median graphs, which is based on Mulder’s convex-expansions technique. Further, we present an \(O(|V|^2 \log |V|)\) algorithm for obtaining an isometric embedding of a median graph \(G\) in a hypercube \(Q_n\) with \(n\) as small as possible.