Eso se saca con teoria de grafos. En 2 dimensiones sin que se crucen es imposible. Hay una formula que determina el numero de nodos necesarios,y en ese caso siempre vas a necesitar uno mas de los que puedes poner. En el caso más óptimo vas a poder colocar 8 sin que se toquen, el noveno te lo comes.
Necesitarias recurrir a una tercera dimension para ello.