I think sometimes typedefs are necessary. I've been in a situation like this before
template<class edge_type, class node_type>
class Graph
{
public:
typedef edge_type EdgeType;
typedef node_type NodeType;
[...]
};
template<class graph_type, class heuristic>
class GraphSearchAlgorithm
{
//this needs access to the edge_type and node_type
}
I don't think they are avoidable in a situation like this. If they are, correct me.
Also, I hate overusing typedefs myself, but sometimes it can be handy to use them when you get to deal with annoying dependant names like A::B::C:

::E::F::G::H::I<J::K::L<M::N:

, P::Q::R< S::T, U::V> >::W::X>::Y::Z ;D
You might think it's good to see where the types come from for example, without having to scroll over the identifier. But sometimes it's really not worth sacrificing the speed and code clarity of using typedefs, especially when dealing with ultra long names. This doesn't mean that you have to make your typedefs global, it can be good to do so within a class or function too, and it will hide outside of those functions/classes
They're also way better than defines for debugging.