Implicit Graph Representation Conjecture and Geometric Intersection Graph Classes

26^th May 2020, 13:00 Microsoft Teams
Dr. Viktor Zamaraev
Department of Computer Science,
University of Liverpool

Abstract

An adjacency labeling scheme for a graph class is an assignment of labels to the vertices of each graph in the class such that the adjacency of two vertices in the graph can be determined solely by the labels of these vertices. The labels are binary strings of the same length and the goal is to make the labels as short as possible.

If one wants to encode node identifiers within the labels, the size of the labels should be \Omega(\log n) bits, where n is the size of the graph. A natural question is what families of graphs admit adjacency labeling schemes with \Theta(\log n) bits. In particular, does every graph family with the "right" number of graphs admit such a labeling scheme? In 1992, Kannan, Naor, and Rudich showed that the answer to this question is negative in general. However, for hereditary graph classes, the question remains open since then.

The aim of this talk is to discuss the Implicit Graph Representation Conjecture, its connection to geometric intersection graph classes, and present some open problems surrounding the conjecture.