Local representations using very short labels Original Research Article

A local representation of a graph is a data structure which places a short label on each vertex of the graph so that adjacency between vertices can be deduced just from the vertex labels. By short we mean that the label consists of O(log n) bits where n is the number of vertices in the graph. It is conjectured (Kannan et al., SIAM J. Discrete Math. 5 (1992) 596–603; Muller, Ph.D. Thesis, Georgia Institute of Technology, 1988) that a hereditary family of graphs P has a local representation provided the number of labeled graphs on n vertices in P is bounded by nkn for some fixed k. Here we develop and prove an analogous result using very short labels on the vertices, i.e., labels with o(log n) bits.