Label placement can be viewed as a problem in computational geometry. Text is usually considered as being enclosed in a bounding box (rectangle). So your task is to pick some aesthetically beautiful locations to try, and test if any of the lines or arcs in your diagram intersect the bounding box.

As you say, aesthetic locations may not always work. As a first try after that failure, I would identify the set of lines coming into a vertex, compute the angles between neigboring lines, and pick the neighboring lines with the largest angle between them to nestle the label into. Given the angle and the size of the bounding box, it is a simple matter of geometry to determine how far away the bounding box should be from the vertex so that it does not intersect each line. I'd expect the center of the bounding box would lie close to the bisector of the two lines.