Graphs of intersections of closed polygonal chains

In the paper such subclass of string graphs as intersection graphs of closed polygonal chains (class of $CPC$-graphs) was considered, necessary conditions for belonging to that class, forbidden subgraphs and operations with graphs which preserve belonging to the $CPC$ class were found. Considered question about the existence of $k$-regular $CPC$-graphs, particularly, pairs $(k, n)$, such that there exists k-regular $CPC$-graph on $n$ vertexes were found, proved that there are infinitely many $k$-regular $CPC$-graphs for any $k\in \mathbb{N}$, estimations for the number of $k$, such that $k$-regular graph on $n$ vertexes exists, were given. Algorithmic questions in the class of $CPC$-graphs were investigated. It was proved that independent and dominating set problems, coloring problem and the problem about maximal cycle are $NP$-hard in the class of $CPC$-graphs, and problem of recognition of the $CPC$-graphs belongs to the $PSPACE$ class.