Vector of vectors (a.k.a. array of arrays)
Using this data structure allows you to consider vertices and edges (specially useful when dealing with one-way streets or roads) and it also let's you consider more efficient maps, leaving out obstacles.
In this case you would use at least two vector of vectors; one for storing the vertices and the edges and the other one for storing node membership to regions (countries, for example).
An extra vector of vectors could be use to store cities that belong to a country, for example. It depends on the specific problem you're targeting.
Data representation for tactical analysis
This technique is great when dealing with grids in order to develop tactical analysis and tag each location as part of a region and such.
Now that you're thinking about graph theory, and developing your graph using Dirichlect domains, this technique comes in handy for tactical analysis and is very similar to having influence maps on a grid.
Nowadays developers are more inclined into these standard formats and there are several file handlers for your platform of choice.
It's good that you research them in depth and decide which one is more suitable to your project.