On the OBDD size for graphs of bounded tree- and clique-width

AbstractWe study the size of OBDDs (ordered binary decision diagrams) for representing the adjacency function fG of a graph G on n vertices. Our results are as follows: –for graphs of bounded tree-width there is an OBDD of size O(logn) for fG that uses encodings of size O(logn) for the vertices;–for graphs of bounded clique-width there is an OBDD of size O(n) for fG that uses encodings of size O(n) for the vertices;–for graphs of bounded clique-width such that there is a clique-width expression for G whose associated binary tree is of depth O(logn) there is an OBDD of size O(n) for fG that uses encodings of size O(logn) for the vertices;–for cographs, i.e. graphs of clique-width at most 2, there is an OBDD of size O(n) for fG that uses encodings of size O(logn) for the vertices. This last result complements a recent result by Nunkesser and Woelfel [R. Nunkesser, P. Woelfel, Representation of graphs by OBDDs, in: X. Deng, D. Du (Eds.), Proceedings of ISAAC 2005, in: Lecture Notes in Computer Science, vol. 3827, Springer, 2005, pp. 1132–1142] as it reduces the size of the OBDD by an O(logn) factor using encodings whose size is increased by an O(1) factor