Data MAY also include Egyptian hieroglyphs not encoded in Unicode. Does it mean that the markup MUST support them as well? I bet not. No format can natively support every possible data structure; serialization formats only have to support enough of them to which remaining structures can be isomorphically mapped.
> a common enough occurrence
Do you have a concrete figure about "common enough"? Otherwise we are only talking through anecdotal evidences (not necessarily bad though!). At least in my experience, graph structures do occur from time to time but almost all of them can be easily rewritten to non-graph form because they are typically DAGs and obviously ranked (i.e. its preferred topological order forms partitions of different nodes). The general graph that requires something like references was very rare.