First of all I'm not at all sure categories have a place in the protocol at all, or for that matter anywhere in core Atom. Categorization on the web is a hard problem with different solutions being more appropriate in some circumstances than others.
I'm a big fan of DAGs, but I think even such a restriction is a step too far. I go along with the idea of the servers using whatever model they wish.
Category - URI - many: memberOfURIs - many: memberURIs (can be entries or categories) - name/title