Logical Labeling Schemes

Abstract

A labeling scheme is a space-efficient data structure for encoding graphs from a particular class. The idea is to assign each vertex of a graph a short label s.t. adjacency of two vertices can be determined by feeding their labels to an algorithm which returns true iff they are adjacent. For instance, planar and interval graphs have labeling schemes. The label decoding algorithm should be of low complexity since the time it takes to execute corresponds to the time to query an edge.

What graph classes have a labeling scheme if the label decoding algorithm must be very efficient, e.g. computable in constant time? In order to investigate this question we introduce logical labeling schemes where the label decoding algorithm is expressed as a first-order formula and consider their properties such as the relation to regular labeling schemes. Additionally, we introduce a notion of reduction between graph classes in terms of boolean formulas and show completeness results.