I'm trying to decompose an arbitrary undirected graph G into minimal subgraphs so that no cycle of the original graph does cross the boundaries of a subgraph. The subgraphs are defined by a partition of edges of G, meaning that each edge is assigned to exactly one subgraph while each nodes is present in all subgraphs that contain at least one edge connected to that node.

Stated another way, two edges are part of the same subgraph if, and only if there is some cycle in G containing both edges.

For example, given the following graph, the blue circles show how eges are grouped into subgraphs:

As a result, decomposing the graph above would yield the following 9 subgraphs:

I've tried to come up with an algorithm by first computing the bridges and articulation points of the graph and then using this information to compute where boundaries between subgraphs lie or something, but without success. Below is the same graph with its bridges and articulation points highlighted in orange:

Is there an efficient algorithm to compute the partition I've described above?

Some background

I'm implementing an algorithm to propagate properties, and changes to those properties, according to some specific rules through a big (e.g. > 10⁶ nodes), static, undirected graph. The algorithm scales with the number of property changes for trees but scales with the number of nodes of the graph if the graph contains cycles.

The graphs I'm working with may contain arbitrary cycles but most of them will be very small (e.g. < 5 nodes) and often not connected to other cycles.

My approach is to use different algorithms for part of the graph that contain cycles and the parts that don't. This works if I can transform the given graph into a tree where each node of the tree either represent a single node of the given graph or a subgraph containing cycles of the given graph.