Way finding/losing in a digital library

I am in a discussion with a programmer about ways to offer navigation using a poly-hierarchical arrangement of nodes. He brought up the concept of directed acyclic graphs (DAG), which is from Mathematics. I learned from the Free Online Dictionary of Computing that the idea is that a directed graph would contain no cycles, i.e. if there is a route from node A to node B then there is no way to cycle or loop back. I can see some applications benefitting from this algorithm, such as in forward citation searching. I think I may not understand the concept entirely, but I am guessing that in an information environment, this means that you'd lose context the deeper you find yourself in a directed path. Or perhaps it simply means you navigate forward to point A from point B and has nothing to do with providing backward movement.

The problem we're experiencing is that we have been dealing with a legacy of organizing by collections/products/services, which is reinforced in our site navigation. Oddly, we don't have problems post-coordinately displaying term combinations in database search results. Rather, in search results we display other terms from the subject taxonomy to narrow results by subject. The problem we have is with the legacy of hierarchical arrangements of access points organized by: collections, services, topics (this uses slices of the subject taxonomy). It's a very library-centric view that we've been dealing with changing, and if you ever worked in a library (corporate, private, special or public) you might know how difficult it is create this type of change.

I've pointed out that the concept of surfacing more facets of index terms would be helpful for browsing. Jim Anderson at Rutgers helped me to buy into this idea while I was in library school, and before I knew much about the web, I advocated this idea in an image index I proposed in 1997. That naive and over-ambitious Filemaker Pro screen shows how I envisioned it. It's funny. Today, I'm wondering how we can support the display of polyhierachical classifications such as our subject taxonomy and other database fields. We have some ideas floating around, but I feel like a toddler trying to topple an elephant.

...

Some follow-up. We're kicking around the idea of a) showing multiple breadcrumbs, and b) showing local navigation for one of the hierarches where the node exists. With the local navigation, we're going to check where the user came from in order to determine which tree to show. If they came from a bookmark or an email (most of our pages are also lined to from email alerts) we will show nothing, unless the node only has one parent, then we will show that tree. This is the theory. We need to test, but interested in opinions. Have you done something like this in a better way?