Treffer: Compact Representation of Graphs of Small Clique-Width.

The notion of clique-width for graphs offers many research topics and has received considerable attention in the past decade. A graph has clique-width <italic>k</italic> if it can be represented as an algebraic expression on <italic>k</italic> labels associated with its vertices. Many computationally hard problems can be solved in polynomial time for graphs of bounded clique-width. Interestingly also, many graph families have bounded clique-width. In this paper, we consider the problem of preprocessing a graph of size <italic>n</italic> and clique-width <italic>k</italic> to build space-efficient data structures that support basic graph navigation queries. First, by way of a counting argument, which is of interest in its own right, we prove the space requirement of any representation is Ω(kn)<inline-graphic></inline-graphic>. Then we present a navigation oracle which answers adjacency query in constant time and neighborhood queries in constant time per neighbor. This oracle uses <italic>O</italic>(<italic>kn</italic>) space (i.e., <italic>O</italic>(<italic>kn</italic>) bits). We also present a degree query which reports the degree of each given vertex in O(klog∗(n))<inline-graphic></inline-graphic> time using O(knlog∗(n))<inline-graphic></inline-graphic> bits. [ABSTRACT FROM AUTHOR]