LAUSR

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 k if it can be represented as an algebraic expression on k 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 n and clique-width k 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 $$\varOmega (kn)$$Ω(kn). Then we present a navigation oracle which answers adjacency query in constant time and neighborhood queries in constant time per neighbor. This oracle uses O(kn) space (i.e., O(kn) bits). We also present a degree query which reports the degree of each given vertex in $$O(k\log ^*(n))$$O(klog∗(n)) time using $$O(kn \log ^*(n))$$O(knlog∗(n)) bits.