Actually, my criticism of global state is based somewhat differently.
It clearly isn't. I'd imagine that if someone asked us to create a list of everything wrong with global variables we would both hit on almost the same points. You only have a less rigid definition for global state than I do.
I consider constant tables, such as those used to implement a state machine for example, as being global state; it is only immutable.
I consider this:
or even this:
#define Initialize 0
#define Finalize 1
#define Advance 2
#define Compare 3
as being global state when more than one single function in a mutually recursive state machine ever uses it. (You have implied that it is global state even when a single function uses it, but I rather doubt that's what you mean.)
I consider passing a "90%" bit of global state around by parameter as global state. Such an "anti-pattern" is still subject to the same criticisms as most any other global state. You are only saying, for whatever reason, that such would not be global state because the function isn't "reaching outside itself". The problem is, by passing the actual global state around you are allowing that function to "reach outside itself" by proxy. You are only trying to disguise it. Hiding that state behind a pointer passed everywhere doesn't change anything. Any function in the chain (not just a function calling another function but even "siblings") can corrupt that global state in a variety of ways and everything "up stream", "down stream", and "sideways" might break because of it exactly as if it had been a simple global variable.
Look for a moment at your graph example. It doesn't really explain why the "Singleton" pattern is bad to a newbie because it would look to a newbie like the data the singleton represents is only accessible by the singleton apparently reducing coupling on global state because fewer links exist between desperate components. (We know it doesn't really do that.) Still looking at that graph example, consider the "pass a pointer everywhere" approach. That's absolutely not the same thing as associating relevant data and putting them into a class. Sure, it looks like the dependencies have a nice hierarchy of responsibilities but by simply passing global state around you've said "links can flow anywhere and everywhere".
Consider function `A' that calls `B' and `C'. Functions `B' and `C' know nothing about each other. Functions `B' and `C' need access to global state. (It doesn't matter what.) Instead of a redesign and rewrite you only wrap the global state with a pointer and pass that into `B' and `C'. `B' and `C' have a real dependency even though it doesn't look like it because `B' or `C' may break that global state causing problems for everyone else.
Now, you can solve that issue, but it means doing the work of designing and using components properly. For example, you might break out the global state that `B' and `C' needs and make that state a class for the interface by having real parameters of the appropriate class type. (Simply explicitly copying that global state and passing copies around solves part of those particular problems.) However, it is clearly more work and exactly why most people will not do it and wind up with global state. I don't mean just in rewrites either; programmers, especially newbies, developing new code will just as often use some form of global state so that they don't have to deal with figuring out and using an appropriate interface.