Ordered binary decision diagrams (OBDDs) are a directed acyclic graph represen-
tation of a Boolean function. They have been used in various areas such as VLSI
CAD, AI, combinatorics, etc. thanks to its good properties. OBDDs can, for in-
stance, represent many of practical functions compactly and have canonical form,
which make it easy to check the equivalence of Boolean functions.
This thesis first proposes an output-size sensitive and work-space efficient algo-
rithm for constructing an OBDD to overcome the drawbacks of the conventional al-
gorithm. Secondly it demonstrates an extended algorithmic framework of applying
OBDDs to combinatorial graph problems by using the algorithm, and, as another
important application of the algorithm, it proposes a new operation, called re-
ordering operation, to change variable ordering of OBDDs in OBDD-manipulating
systems. Thirdly, it shows that fertile concepts, i.e., bandwidth, decomposition,
and separators, of graph theory have much relation to the width of the correspond-
ing OBDD. In fact, for some combinatorial graph problems, the relation gives
subexponential upper bound of the width of the OBDD, and the limit to make the
OBDD size polynomial, in the number of variables. Furthermore it is also touched
on that the relation is strongly connected with other interesting areas such as linear
programming and logic design.