Abstract Binary Decision Diagram (BDD), proposed by Akers, is a directed acyclic graph, which represents many boolean functions efficiently. After Bryant proposed an efficient algorithm to manipulate them, BDD is used not only in logic design area, but also in combinatorial problems. The size of a BDD sometimes highly depends on its variable ordering and the size of an intermediate BDD also depends on the operation ordering. It is, therefore, important to find a good variable ordering and an operation ordering. In this paper, we take an independent set problem. It is easy to construct a BDD of independent sets, but it is difficult to construct a BDD of maximal independent sets. We present an algorithm to construct a BDD of maximal independent sets of a graph from a BDD of independent sets of it and consider the size of the BDD and operation ordering. As a result, we found that our algorithm reduced the size of the intermediate BDD. The resulting BDD represents prime implicants of a boolean function, therefore this problem is regarded as a problem of generating prime implicants of a negative 2-CNF function. Besides, this approach can be used for counting the number of triangulations and we found BDD represents the solutions compactly.