Ich würde in die
XML-Datei zwei Haupt-Nodes einfügen: eine Liste der einzelnen Knoten und eine Liste der Kanten.
Beim Abspeichern der Knoten bekommt jeder Punkt einen Index, der temporär im Knoten abgelegt wird. Beim Speichern der Kanten werden die Knoten-Indizes geschrieben.
Bei Einlesen werden zunächst alle Knoten der Reihe nach in ein Array geschrieben. Damit kann beim Einlesen der Kanten jeder Knoten über seinen Index mit O(1) gefunden werden.
Nur so ein Gedanke...