# Maximum number of not overlapping cycles in an undirected graph

Basically, when given an Undirected graph, the problem of getting maximum cycles is known.

This case is quite different. The graphs I'm dealing with are made by converting geometric polygons to vertices and edges, so vertices relative position matters, and there are weights on the edges representing the distance between 2 vertices.

The are 2 problems:

• Problem 1:

finding the maximum number of polygons that doesn't share area (not overlapping) but can be tangential to each other.

for example: as you can see, the the above graph has a maximum of 5 not overlapping cycles:

1. purple - (a,b,e,x,d,a)
2. green - (d,x,n,f,k,i,d)
3. orange - (x,e,f,n,x)
4. pink - (b,c,g,f,e,b)
5. red - (f,g,h,m,k,f)

My way of tackling this was:

Given a Graph G = (V,E). randomly pick a vertex v and

(1) execute DFS(v) on it, hoping it will eventually reach v and that would be the one of the cycles.

meanwhile, for every vertex u it encounters, execute (1).

I'm think it's a good way but I hope to find better (neater) solutions from you.

• Problem 2:

finding the maximum number of polygons that doesn't share area (not overlapping) but can be tangential to each other, and for each polygon, it's perimeter is bigger than some pre-defined threshold.

For that problem, I can honestly say I have no clue on how to solve it. ;)

I'll be happy learn about solutions for both problem 1 and problem 2

Thanks!