To tell you the truth, my advice is to fight the requirement for multiple parentage. I've worked on a number of projects that mapped complex hierarchies, and this multiple parents idea seems to come up a lot. It's usually a red herring. It looks like it will solve a certain problem, but in the end it hopelessly confuses users and dramatically complicates code.

People often think this is the way to handle cross-linked hierarchies. I think what Yahoo does makes more sense, essentially having symlinks to the other nodes rather than a standard parent-child relationship. Having multiple parents means you can never know your context (for something like a breadcrumb trail back up to the root node) without keeping a complete history of every node a user has visited on the way to this one.

The last time I had a problem like this was at an e-commerce site (see if you can guess which one) where we were trying to deal with the fact that a section like "new Pokemon junk" might need to show up under multiple areas in the store and the merchants controlling it don't want to keep track of that and double enter it. An obvious requirement for multiple parentage, but I saw all kinds of implementation problems with it. After trying various things, I ended up making two trees, one for concepts like "new Pokemon junk" with products attached, and one for site layout. The nodes on the concept tree were mapped many to many onto nodes of the layout tree. It sounds complex, but it was less confusing than multiple parentage and it was plenty fast in oracle.