We discuss an open problem in ROBDD construction using composition and prove that the worst case complexity of the construction is truly cubic. With this insight we show that the process of composition naturally leads to construction of (even exponentially) compact partitioned-OBDDs (POBDDs)[17]. Our algorithm which incorporates dynamic partitioning, leads to the most general (and compact) form of POBDDs - graphs with multiple root variables. To show our algorithm is robust and practical, we have analyzed some well known problems in Boolean function representation, verification and finite state machine analysis where our approach generates graphs which are even orders of magnitude smaller.