I'm studying the Sipser textbook for my theory of complexity class. In a part of the book (i.e., Space Complexity chapter), for showing that Generalized Geography game is PSPACE-complete, the author has given an argument to model this game with TQBF problem (which is proven to be PSPACE-complete).
In a step of the argument, he has tried to construct a directed graph by using the definitions of TQBF problem (universal and existential quantifiers). What he has come up with is the following graph:
I have some questions about this graph:
- I, actually, don't get it why the diamond structure has been used for showing choice possibilities of player $x_i$. Couldn't we use a simple structure like what we do on binary trees?
- How would it be if we use a hexagon shape instead of diamond for showing choices of $x_i$?