PDF《1 Introduction》

s theorem [War68]. Roughly speaking, if adjacency in a graph class can be described by a set of polynomial inequations then it is small [Spi03, p. 54];

we give a possible formalization of this later on by what we call polynomial- boolean systems. This method can be used to show that certain geometrical intersection graph classes are small. Examples include line segment graphs, disk graphs and k-dot product graphs. All of the previous examples are hereditary and unknown to have a labeling scheme and thus are candidates for the IGC. The geometrical representations of these classes suggest potential labeling schemes. For instance, in the case of line segment graphs one could assign each vertex four numbers which represent the coordinates of the two endpoints of its line segment in the plane. However, this would only yield a correct labeling scheme if O(log n) bits su?ce to encode the coordinates for every line segment graph. In [MM13] it is shown that this does not hold because there are line segment graphs whose geometrical representation requires an exponential number of bits. They prove that this lower bound also holds for disk graphs. In [KM12] it is shown that the geometrical representation of k-dot product also requires an exponential number of bits. Therefore for none of these graph classes their geometrical representation yields a labeling scheme as opposed to the case of interval graphs. In [Atm+15] certain combinatorial tools are introduced that allow to infer

2 that a hereditary graph class is small. By applying these tools they reveal candidates for the IGC which are de?ned in terms of their forbidden induced subgraphs. Coming from the other direction, one can try to identify sets of graph classes that have labeling schemes. In [Sch99] it is shown that every tiny, hereditary graph class has a labeling scheme where the labels require only a constant number of bits. In [Spi03, p. 165] and in [CV03] labeling schemes for graph classes with bounded clique-width are constructed. In both cases the label decoding algorithm........