Polygon-circle and word-representable graphs

We describe work on the relationship between the independently-studied polygon-circle graphs and word-representable graphs.
A graph G = (V;E) is word-representable if there exists a word w over the alpha-
bet V such that letters x and y form a subword of the form xyxy or yxyx
i xy is an edge in E. Word-representable graphs generalise several well-known
and well-studied classes of graphs [2,3]. It is known that any word-representable
graph is k-word-representable, that is, can be represented by a word having exactly k copies of each letter for some k dependent on the graph. Recognising whether a graph is word-representable is NP-complete ([3, Theorem 4.2.15]). A polygon-circle graph (also known as a spider graph) is the intersection graph of a set of polygons inscribed in a circle [4]. That is, two vertices of a graph are adjacent if their respective polygons have a non-empty intersection, and the set of polygons that correspond to vertices in this way are said to represent the graph. Recognising whether an input graph is a polygon-circle graph is NP-complete [5]. We show that neither of these two classes is included in the other one by showing that the word-representable Petersen graph and crown graphs are not polygon-circle, while the non-word-representable wheel graph W5 is polygon-circle. We also provide a more refined result showing that for any k 3, there are k-word-representable graphs which are neither (k - 1)-word-representable nor polygon-circle.