In a graph of `N` ternary nodes represented as an adjacency table of delta positions, is it possible to minimize the maximum value on the table?

Question

Let's define a graph to be a set of N nodes, where every node has exactly 3 outgoing edges. Such graph can be represented as a table of adjacency, using delta positions to denote edges. For example, the graph:

Could be represented as:

       0   1   2
A: 0  +1  +2  +1
B: 1  -1  -1  +1
C: 2  +1  -1  -2
D: 3  -1  +0  -0

On the first row, we have +1, +2, +1, because A has edges to B, C, B respectively, which are at 1, 2, 1 rows behind A, respectively. Similarly, B's first edge is -1, because it goes to A, which is on the previous row. There are multiple ways to represent the same graph, by rearranging rows. Let's define the weight of a graph under a particular representation as the largest absolute value on the table representing it. Let's define the optimal representation as the one with the smallest weight. Let the heaviest among a set of graphs be the one with the largest optimal weight.

My question is: given a N and the heaviest graph of that size, what is the minimum weight W(N) of its optimal representation?

Obviously, any representation of a graph of size N must have a weight of at most N. But how small can it get? In particular, I'm interested in answering if, for large graphs (say, size 1000), we can always find a representation with a low weight (perhaps logarithmic on the size of the graph?).

Answer 1

We cannot always find a representation with a low weight.

A graph that's really hard to represent is a graph with small diameter (the value $d$ such that any two vertices are connected by a path of length at most $d$). If you have an $n$-vertex graph with diameter $d$, then no matter how you label the vertices, there will be a path of length $d$ or less from vertex $1$ to vertex $n$; this means at least one of the edges on that path has a weight of at least $\frac{n-1}{d}$.

It's possible to construct $3$-regular graphs on $n$ vertices with diameter $O(\log n)$. In fact, a random $3$-regular graph is likely to have such a diameter. This short paper gives an explicit construction for $n$-vertex $3$-regular graphs with diameter about $1.413 \log_2 n$.

So we can find many examples of $n$-vertex $3$-regular graphs for which the minimum weight of any representation is $O(\frac{n}{\log n})$.