Another way to use graphs is to represent how much reach or influence an agent, or, in this case, a unit, has over an area of the world. In this context, influence is represented as the total area of a map covered by an agent, or a group of agents from the same party.
This is a key element for creating good AI decision mechanisms based on top of military presence in real-time simulation games, or games where it is important to know how much of the world is taken up by a group of agents, each representing a given faction.