The goal: minimize the badness, defined as the sum of squares of difference between vertex valence and desired valence. The desired valence for boundary vertices is whatever they start at; for interior vertices it is 6. You can perform any of the following 3 operations repeatedly:

Vertices with too many edges are green, those with too few are red.
Rules of thumb:

This is based on this Delaunay Triangulation script. Note that my code works very slowly in Internet Explorer due to event handling.

Creative Commons License
This work is dedicated to the Public Domain.