An algorithm for the maximum weight independent set problem on outerstring graphs

Given an outerstring graph and an intersection model consisting of polygonal arcs with a total of N segments, we develop an algorithm that solves the Maximum Weight Independent Set problem in O(N3) time. If the polygonal arcs are restricted to single segments, then outersegment graphs result. For outersegment graphs, we solve the Maximum Weight Independent Set problem in O(n3) time where n is the number of vertices in the graph.