TY - JOUR

T1 - Logical labeling schemes

AU - Chandoo, Maurice

N1 - Funding Information: I would like to thank Viktor Zamaraev for many stimulating discussions on the subject and for helping me understand the proof behind the refutation of the Implicit Graph Conjecture as well as the anonymous reviewer for giving me valuable feedback to improve the quality of this paper and pointers to relevant results in the literature that I missed.

PY - 2023/10

Y1 - 2023/10

N2 - A labeling scheme is a space-efficient data structure for encoding graphs from a particular graph class. The idea is to assign each vertex of a graph a short label s.t. adjacency of two vertices can be algorithmically determined from their labels. For instance, planar and interval graphs have labeling schemes. The algorithm used to determine adjacency—called label decoding algorithm—should be of low complexity since the time it takes to execute corresponds to the time to query an edge in that representation. 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 labeling schemes defined in terms of classical complexity classes. Additionally, we introduce a notion of reduction between graph classes in terms of boolean formulas and show completeness results.

AB - A labeling scheme is a space-efficient data structure for encoding graphs from a particular graph class. The idea is to assign each vertex of a graph a short label s.t. adjacency of two vertices can be algorithmically determined from their labels. For instance, planar and interval graphs have labeling schemes. The algorithm used to determine adjacency—called label decoding algorithm—should be of low complexity since the time it takes to execute corresponds to the time to query an edge in that representation. 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 labeling schemes defined in terms of classical complexity classes. Additionally, we introduce a notion of reduction between graph classes in terms of boolean formulas and show completeness results.

KW - Graph class reduction

KW - Implicit representations

KW - Structural graph theory

UR - http://www.scopus.com/inward/record.url?scp=85162127926&partnerID=8YFLogxK

U2 - 10.15488/11960

DO - 10.15488/11960

M3 - Article

AN - SCOPUS:85162127926

VL - 346

JO - Discrete mathematics

JF - Discrete mathematics

SN - 0012-365X

IS - 10

M1 - 113565

ER -