Geometric Realizations of Dichotomous Ordinal Graphs

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 Rk or the sphere Sk, respectively. First, every d-degenerate graph is pandichotomous in Rd and Sd-1 and these bounds are tight for the sphere and for R2 and almost tight for Rd, for d ≥ 3. Second, every n-vertex graph that is pandichotomous in Rk has at most μkn edges, for some absolute constant μ < 7.23. This shows that the pandichotomic Euclidean dimension of any graph is linearly tied to its degeneracy and in the special case k ∈ {1, 2} resolves open problems posed by Alam, Kobourov, Pupyrev, and Toeniskoetter. Further, we characterize which complete bipartite graphs are pandichotomous in R2: These are exactly the Km,n with m ≤ 3 or m = 4 and n ≤ 6. For general bipartite graphs, we can guarantee realizations in R2 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.