How accurate do you want to be? A good but complex choice would be simulating all that history:
- Generate a random region list and adjacencies between these regions.
- Generate random civilizations with characteristics such as population, belligerence, technology... and populate the regions.
- Simulate as many years of history as you want, determining outcomes based on civilization characteristics.
E.g.: two adjacent belligerent civilizations have a higher probability of starting a war on each other, which leads to lower population over time. Merchant civilizations have higher resources, but are a great target for invasions. Highly populated ones will grow faster but also have more chances of hunger. Culturally-heterogeneous civs have a lower chance of internal wars (which could lead to breakups.) And so on... Outcomes would also modify the civilization characteristics: higher technology leads to better trading, stronger weapons, etc.
This allows for some procedural storytelling too: you can output not only a territory diagram, but also textual descriptions of history throught time. You can make this system as complex as you want.
EDIT: the challenge here is not a technical one, but adjusting the heuristics for realistic and interesting history generation. Take a closer look and think about the 3 aforementioned points... that's pretty much your technical explaination! Translate it to a loop (each iteration can represent as much time as you want, 1 year, half a year, 1 month...) and that's it. You'll have to work the inners (data structures, heuristics) and adapt it to your specific problem and needs. That's the hard part here and nobody can help you, since it's about imagination, trial and error.
There are no common data structures for this problem besides the ones you'll use for almost any problem: lists, queues, trees... and these will be tied for your specific implementation (do I need a genealogic tree? a list of civilizations at war? a queue of tasks for each civ?) Of course you need a list of civilizations too. The choices are obvious and pretty much common sense.
Simulation is a matter of chance/probability and you can make it a thousand different ways with random numbers. Think of any other game where simulation is involved like football managers, RPGs (after all, hitpoints/stats is just combat simulation), strategy games... It's just characteristics (so you'll need a way to store civilization characteristics and data) and random outcomes statistically based on them (so you'll have to randomly change the simulation state based on these characteristics.)
That's the essence of your algorithm: the hard to adjust heuristics: how to distribute characteristics at the beginning of the simulation for each civilization and how to statistically change the simulation state based on them.
In short: your algorithm is just a loop ranging the simulated time with any desired increment. Shorter increments lead to finer historic simulation, but will obviously take longer. Inside your loop there will be a bunch of heuristics like (roughly):
for each civilization
civ.population -= civ.population * 0.05;
civ.wealth -= 1000.0;
civ.belligerence += 1.0;
if civ.population < 100
After all this work (or during if you don't want to store the data) you must interpret all the simulation state into human-readable format like text, images or whatever you desire. This is trial and error too and very specific for your implementation.
Specific to your question: to generate a diagram like the one in your question you'll have to track world regions (top of the diagram, x axis, that's point 1: generate region list in my answer) and their civilizations (colors in the diagram, point 2) through time (y axis, the simulation loop in point 3.)
State machines are quite good at simulating broad topics (the code sample above is an approximation of a hard-coded state machine) - so you might start by implementing a simple state machine framework that is overall easy to tweak. Each civilisation would start off with one of these state machines and the simulation would run each state machine for each turn. Each state machine would need to be able to interact with other state machine: for example initiating a war would affect another civilisation's state machine, possibly with different outcomes based on their internal state - e.g. if they are in the 'famine' state they would likely want to negotiate peace, but a civilisation 'looking for trouble' would likely retaliate. Each state in the machine would have meaningful effects on the civilisation's metrics outlined above during each 'frame' (wealth, belligerence, populace, etc.). Most importantly you do not need to transition states on every frame - just when opportunity and/or random chance arises: this allows prolonged events (like war) to occur.