I am (slowly) writing a review of the Handbook of Chemoinformatics Algorithms for SIGACT News. One chapter discusses current software implementations, and the database searches (and other applications) don't seem to take advantage of as much information about the graphs as they could. On the other hand, perhaps more theoretical algorithms would be too hard to implement. It seems like a potential open area, though.
So here's my question:
Is there an overview (or a small handful of references) that discusses theory and implementation (hopefully) of algorithms of databases of graphs with metric information? (Each edge is a distance, and each vertex has a volume.) A chemistry-free description of an example problem would be: given a database of graphs, find all of them that contain a particular subgraph.