If you put base stations (towers) too close, they must not interfere with each other. Hence, they must work on different frequencies. This is where graph coloring is used. An each distinctive color will represent each distinctive frequency.
Represent towers as vertices. If towers are placed too close to each other, put an edge between them, meaning, different colors/frequencies must be assigned to them.
Now this is why cellular network is a cellular network -- placing stations/tower in hexagonal form, makes this graph to be colored using only two colors/frequencies:
(Pardon my miserable Photoshop skills.)
Mathematicians say, the chromatic number of this (planar) graph is 2. Chromatic number is a minimal number of colors. And a planar graph is a graph that can be represented on 2D plane with no edges intersected (like a world map).
Hexagonal grid is hence optimal for the task. This is not achievable in practice (you cannot place towers in city wherever you want), but you can come close to this ideal.
→ [list of blog posts]Please drop me email about any bug(s) and suggestion(s): dennis(@)yurichev.com.