Optimising updates to a way point graph

I have a graph of vertices and connected edges as shown in the image below.

I have a function that iterates from every single vertex and finds closed loops in order to find all polygons in the graph.

Here is an example of my graph which has found all the polygons in the graph:

Now if i add a new segment (seen in red)

What i currently do is basically wipe my array of all polygons found, and find all polygons again.

But this is clearly not needed because not all polygons are going to need to be updated here.

How can I optimise my function so I can avoid checking the entire graph again?

Its obvious P2 doesn't exist anymore, its been cut into two new polygons. And P3 and P4 only needs an edge inserted into its array of edges. And P1 is unchanged.

I only want to check the minimum amount of vertices that will find all the new polygons and changes to pre-existing ones. But I am not sure which vertices have to be rechecked besides the two new ones added on each end of the red edge added to the graph.

I have a graph ...

I read that as "a planar graph".

You didn't describe your analysis data structures, so I will make some assumptions. Let U be the initial undirected graph, and G the corresponding digraph where each edge becomes a pair of edges, forward + backward. Now we have suitable input for a python method to use Johnson[1975], simple_cycles() in networkx. The cost of (n + e) × (c + 1) is on the expensive side for a graph with many polygons, but we incur the cost just once, and I don't see how to get away with doing less work.

Maintain a set of cycles. Given a cycle, lexically order its nodes, so the 1st node could name the cycle, could name the polygon. Or if you prefer, tack on a mapping and generate P1 .. Pn names as each polygon (cycle) is added and deleted.

Maintain a cycle_member attribute on each node. Notice that it is a set. One of your example nodes is member of {P1, P2, P4}.

2. From those affected nodes, find the dominant cycle_member cycle, which all those nodes are in.
5. Compute both simple_cycles.
6. Visit the nodes of both cycles, updating each cycle_member attribute.