Optimising updates to a way point graph

Question

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.

Answer 1

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}.

---

add a new segment

1. Find the set of affected nodes (four, in your red segment example).
2. From those affected nodes, find the dominant cycle_member cycle, which all those nodes are in.
3. Remove that cycle from all nodes in the cycle (P2, in your example).
4. Construct a small new digraph from that cycle plus new edge.
5. Compute both simple_cycles.
6. Visit the nodes of both cycles, updating each cycle_member attribute.

This scales to large graphs, where most cycles and most nodes are distant from the inserted edge. In a graph with a million polygons, the update avoids touching nearly all the cycles and nearly all the nodes.