Assume a planar graph G, and all its vertices have degree at most 4.
Consider a cycle in G. The weight of cycle c is the total weight of its vertices, and a vertex is weighted with the following manner:
For example look at vertex v, if cycle c traverses vertex v by passing through e2 and e4 then it would cost w1 and if it traverses v by passing through e4 and e3 then it would cost w2 and so on! (G is undirected, so traversing v by passing through e4 and e3 costs the same as traversing v by passing through e3 and e4, and all possible traversal from a vertex contain weights; some of them are showed with pink curves in pic.)
1-What is the complexity of finding a cycle with total weight k? (k is a given value)
2-Is finding weighted cycles in G harder than finding cycles in general weighted graphs?
this is also the link of pic: