Maybe you can use scipy.spatial.Delaunay?
Here is some untested code.
Aric
from scipy.spatial import Delaunay
import networkx as nx
# nodes and positions
nodes = list('abcde')
points = [(0,0),(7,7),(5,5),(1,7),(3,4)]
t = Delaunay(points)
edges = []
m = dict(enumerate(nodes)) # mapping from vertices to nodes
for i in range(t.nsimplex):
edges.append( (m[t.vertices[i,0]], m[t.vertices[i,1]]) )
edges.append( (m[t.vertices[i,1]], m[t.vertices[i,2]]) )
edges.append( (m[t.vertices[i,2]], m[t.vertices[i,0]]) )
print edges
# build graph
G = nx.Graph(edges)
pos = dict(zip(nodes,points))
# draw
import matplotlib.pyplot as plt
nx.draw(G,pos)
plt.show()