I'm exploring heuristics in A* and apparently all heuristics require coordinates of all the locations to calculate a h-cost. This is fine if you are working on grids, but what if you need to work solely on graphs where "traveling in a straight line" doesn't make sense at all?
Are there any heuristics that works solely on graphs (i.e. without requiring coordinates of the locations)?
There are known pre-processing methods that rely solely on the graph representation itself (and not on any kind of geometric embedding) to establish good heuristics for A*. Perhaps the most well-known example in recent research is called ALT (A* + Landmarks + Triangle-Inequality). Here is one of the original papers on this topic: https://www.microsoft.com/en-us/research/publication/computing-the-shortest-path-a-search-meets-graph-theory/
There has since been much further research on expanding and improving upon the heuristics used by the ALT technique. A simple search on this topic should turn up plenty of more-recent and relevant results (I tried posting links to some of them here, but the system has unfortunately limited the number of links I can provide in my response).
Aside from ALT, there has also been subsequent research on alternative techniques for constructing other similar heuristics purely from the graph representation (which is directly compared to ALT as well): http://www.aaai.org/ocs/index.php/SOCS/SOCS12/paper/view/5372/5180
