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

Abstract

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.