Uma dúvida: de onde tirou estes termos? Lá não tem dicas de como usar?
Acho que para cada coisa que você faz com grafo e dependendo do tipo do grafo você usa um determinado recurso de armazenamento.
Meu uso de grafos é para renumerar os nós. Para o meu uso, vetor de adjacência + vetor índice das adjacências dispensa o uso de matriz de incidência e substitui a matriz de adjacência (com vantagens no armazenamento).