Without giving too much away, I wanted to share an early example of the types of story graphs I'm working on for my thesis. This was my first example, and it's inspired by Robert Munsch's Paper Bag Princess.
Without even telling you what all the colours and notations mean, you can probably gather that there are some nodes that must be seen in a particular order, and others that can be seen any time.
Eventually my examples will have much more of the latter type. The end goal is to be able to decide which nodes should be available in the first place according to the player's current state in the game, and then to dynamically modify the scenes in small, simple ways to ensure they make sense and connect back to previously seen nodes.
Hopefully, this will result in more open and coherent emergent stories in games.