Stephen Wolfram, in "A New Kind of Science", attempts to remove the assumption of an underlying space from his cellular automata by devising automata that operate on networks. This approach is also being followed by some physicists. The idea is that space will emerge implicitly from the network updating rules.
To specify a linkage from one node to another in a network, you have to have some way to identify those nodes. Such identification requires O(log(n)) bits, where n is the size of the network. Wolfram limits himself to nodes with three connections each, however even these simple nodes may require arbitrarily large amounts of information to specify, if the network is allowed to become arbitrarily large.
This feels wrong.
The idea might be salviagable though. Suppose for each node, instead of listing the identity of other nodes that it connects to we just listed some connectivity information. eg: Neighbour1 links to me, Neighbour2 links to Neighbour1, Neighbour3 links to Neighbour2 and me. This would mean a small, finite amount of information per node. I'll call this representation a "routework". (Note: the neighbours of a node are assigned a definite order in a routework)
A routework might be built, starting from a single node, by some node-substitution system that ensures all affected nodes maintain information that is complete and self-consistent. This would guarantee the routework as a whole to fully and consistently describe a network. Such rules can be described in finite bits.
A routework can be represented as a string of bits -- start by queueing an arbitrary node, then for each node in the queue output its description and add any as-yet unqueued nodes to the end of the queue. This representation is decodable into the original routework. Any routework can be represented in this way using O(n) bits, whereas general networks can only be represented in O(n*log(n)) bits.
From this we can see that the routework must place some restriction on the form of network it can describe -- perhaps an upper limit on the dimension of the network. In a network, any node can link to any other, and small world phenomena can occur (eg hyper-cube structured networks). So just using this representation gets us half-way to a spatial network.
Question: How much such information suffices to allow the full structure of the network to be inferred, for networks with various properties?