It comes up to my mind when I am thinking of assigning postal codes. The adjacent areas shall be assigned postal codes with small difference. Is there an efficient way to do this labeling stuff?
Mathematically, given a connected undirected graph $G = (V,E)$ and a limit $l$, we want to find a approach to label $1...|V|$ on to the vertices, say $v_i$ for the label for vertex $i$. The labeling is subject to $|v_i-v_j| \leq l$, where $(i,j) \in E$.
I am considering solving this problem using dynamic programming, but have not come up with an idea.
This isn't an answer, but it's too long for a comment. I've done some Googling, and it turns out that the variant I suggested is a well-known problem called the Graph Bandwidth Problem. According to Wikipedia, "In graph theory, the graph bandwidth problem is to label the $n$ vertices $v_i$ of a graph $G$ with distinct integers $f(v_i)$so that the quantity $\max \{|f(v_i)-f(v_j)|:v_i, v_j \in E \}$ is minimized, where $E$ is the edge set of $G$."
Let $\phi(G)$ be this minimum value. $\phi(G)$ is called the "bandwidth" of G. Unfortunately, according to the article, the problem of computing $\phi(G)$ for a general graph G is NP-hard. Even worse, approximating $\phi(G)$ to within some constant multiple is also NP-hard. There are some positive results for particular graphs, and apparently some heuristic algorithms, at least in some cases.
I don't know any more about this, but some of the links in the Wikipedia article might be interesting. I found one of them, "An Exponential Time 2-Approximation Algorithm for Bandwidth," on ArXiv, and it's as disheartening as it sounds. The worst-case time $O(1.9797^n).$ It starts out with a fairly lengthy statement of prior results, and that may be of interest. It states that the bandwidth problem is NP-hard, even for trees of maximum depth 3, and for various other rather simple graphs.
If this is a practical problem, it seems to me that the first thing to do would be to analyze the graphs whose bandwidth you want to compute, to see if they have some special features that might help. If you're talking about postal codes for instance, then I imagine the graph is planar, and there is a bound on the bandwidth given in the article. (It's plainly a rotten bound, though. Compare to the value given for the square grid graph, which is planar.) Also, I'd expect the graph to be sparse. This is more promising, since it looks like there has been more work done on sparse graphs, though I'm reading between the lines somewhat when I say this.