Implicit Representation of Graphs

How to represent a graph in memory is a fundamental data structuring question. In the usual representations of an n -node graph, the names of the nodes (i.e. integers from 1 to n ) betray nothing about the graph itself. Indeed, the names (or labels) on the n nodes are just log n bit place holders to allow data on the edges to code for the structure of the graph. In our scenario, there is no such waste. By assigning Ο (log n ) bit labels to the nodes, we completely code for the structure of the graph, so that given the labels of two nodes we can test if they are adjacent in time linear in the size of the labels. Furthermore, given an arbitrary original labeling of the nodes, we can find structure coding labels (as above) that are no more than a small constant factor larger than the original labels. These notions are intimately related to vertex induced universal graphs of polynomial size. For example, we can label planar graphs with structure coding labels of size < 4log n . This implies the existence of a graph with n 4 nodes that contains all n -node planar graphs as vertex induced subgraphs (It was not previously known that this class had polynomial sized universal graphs). The theorems on finite graphs extend to a theorem about the constrained labeling of infinite graphs.

Authors

• Sampath Kannan
• Moni Naor
• Steven Rudich

Keywords

No keywords are indexed for this paper.