Talvez isso atenda aos seus requisitos? A idéia básica é ter uma matriz (chamada rótulos) que contém o que é efetivamente o número da linha da última linha, começando com um número específico de estrelas. Ele produzirá o gráfico errado se você aumentar o número de estrelas em mais de um, mas lidar com diminuições de qualquer número corretamente. Claro que não lida com texto sob os títulos.
#!/bin/bash
typeset -a labels
typeset -i node=1
while read -r stars rest
do
level=${#stars}
labels[level]=$node
printf '<mxCell id="b%d" value="%q" ></mxCell>\n' $node "$rest"
case $level in
(1) ;;
(*) printf ' <mxCell id="a%d" source="b%d" target="b%d">\n' $((node-1)) $node ${labels[level-1]} ;;
esac
: $((node++))
done