How to plot tree/graph/web data on gnuplot?

I have a data-set that consist of edges and colors, and I want to plot them on a web-like manner, with lines and circles such as the picture below, and possibly with cluster coloring.

Graph example

The data is organized like this:

point1a_x point1a_y color
point1b_x point1b_y color

point2a_x point2a_y color
point2b_x point2b_y color
(...)

point2n_x point2n_y color
point2n_x point2n_y color

How would I go about doing it on gnuplot?

Solution

The accepted answer didn't quite work out for me. Here is how I had to change it:

The format of the input file

# A vertex has 3 fields: x coordinate, y coordnate and the label
# An edge consists of two points in consecutive lines
# There must be one or more blank lines between each edge.

21.53 9.55 A
24.26 7.92 B

5.63 3.23 C
2.65 1.77 D

5.63 3.23 C
4.27 7.04 E

#...

The big difference compared to the other answer is that the labels belong to vertices, not edges.

Also note that I changed the labels to letters instead of numbers. Labels can be any string and this makes it clearer that they are not sequential indexes in the example.

The plotting command

plot \
  'edges.dat' using 1:2       with lines lc rgb "black" lw 2 notitle,\
  'edges.dat' using 1:2:(0.6) with circles fill solid lc rgb "black" notitle,\
  'edges.dat' using 1:2:3     with labels tc rgb "white" offset (0,0) font 'Arial Bold' notitle

Big change here is that now when plotting the labels we plot the 3rd field instead of the $0 field, which is a sequential number.