Before revision:  Inserting a segment amounts to delete all the triangles it intersects , define two polygons that fill the so generated hole and have the segment as shared basis, and then re-triangulate each polygon separately.
After revision:  Inserting a segment amounts to delete all the triangles it intersects , define two polygons that fill the so generated hole with two polygons that have the wanted segment as shared basis, and then re-triangulate each polygon separately.