libxml2 é a biblioteca compartilhada de tempo de execução, adequada para executar programas já compilados que usam essa biblioteca. Se você deseja compilar programas que usam libxml2 , você precisa instalar o libxml2-dev .
Isso vale para a maioria dos pacotes de bibliotecas no Ubuntu (e debian, mint, etc. RH e outros possuem convenções similares) - libfoo é a biblioteca compartilhada de tempo de execução, libfoo-dev contém os cabeçalhos de desenvolvimento e .a archive
Para libz, o pacote é zlib1g-dev
BTW, python-igraph 0.6.5-1 é empacotado para debian - você tem certeza de que ele não é pré-empacotado para o Ubuntu? Se estiver, é muito melhor instalar o pacote ubuntu.