Geometric realizations of dichotomous ordinal graphs

Abstract

A dichotomous ordinal graph consists of an undirected graph with a partition of the edges into short and long edges. A geometric realization of a dichotomous ordinal graph $G$ in a metric space $X$ is a drawing of $G$ in $X$ in which every long edge is strictly longer than every short edge. We call a graph $G$ pandichotomous in $X$ if $G$ admits a geometric realization in $X$ for every partition of its edge set into short and long edges. We exhibit a very close relationship between the degeneracy of a graph $G$ and its pandichotomic Euclidean or spherical dimension, that is, the smallest dimension $k$ such that $G$ is pandichotomous in ${\mathbb{R}}^k$ or the sphere ${\mathbb{S}}^k$, respectively. First, every $d$-degenerate graph is pandichotomous in ${\mathbb{R}}^d$ and ${\mathbb{S}}^{d-1}$ and these bounds are tight for the sphere and for ${\mathbb{R}}^2$ and almost tight for ${\mathbb{R}}^d$, for $d\ge 3$. Second, every $n$-vertex graph that is pandichotomous in ${\mathbb{R}}^k$ has at most $\hat{I}¼kn$ edges, for some absolute constant $\hat{I}¼<7.23$. This shows that the pandichotomic Euclidean dimension of any graph is linearly tied to its degeneracy and in the special cases $k\in \{1,2\}$ resolves open problems posed by Alam, Kobourov, Pupyrev, and Toeniskoetter. Further, we characterize which complete bipartite graphs are pandichotomous in ${\mathbb{R}}^2$: These are exactly the $K_{m,n}$ with $m\le 3$ or $m=4$ and $n\le 6$. For general bipartite graphs, we can guarantee realizations in ${\mathbb{R}}^2$ if the short or the long subgraph is constrained: namely if the short subgraph is outerplanar or a subgraph of a rectangular grid, or if the long subgraph forms a caterpillar.

20 pages, 9 figures, accepted to Symposium of Computational Geometry 2025