Disconnected graphs and extremal bounds for realizable distance orders

Abstract

Let $G$ be a graph together with a total order $\prec$ on its edges. We say that $\prec$ is realizable in ${\mathbb{R}}^d$ if there is a placement of the vertices of $G$ in ${\mathbb{R}}^d$ such that the Euclidean lengths of the edges induce exactly the order $\prec$. Almendra-Hernández and Martínez-Sandoval proved that every total order on the edges of the complete graph $K_n$ is realizable in ${\mathbb{R}}^{n-2}$. We show that the same is not true for the disjoint union of two complete graphs: for every $n\ge 3$ there is a total order on the edges of $K_n\bigsqcup K_n$ that is not realizable in ${\mathbb{R}}^{n-2}$, but is in ${\mathbb{R}}^{n-1}$. Surprisingly, the realizability of an order on a disconnected graph is not determined by its restrictions to the connected components. We also study realizability on the real line: we characterize which disjoint unions of two cycles are realizable, and estimate the largest number of edges an $n$-vertex graph can have while all of its edge-orders remain realizable on the line. In general dimension, we show that the largest number of edges of an $n$-vertex graph all of whose edge-orders are realizable in ${\mathbb{R}}^d$ is $dn+O\left(dn/\ln (dn)\right)$.