Polygoncircle and wordrepresentable graphs
Enright, Jessica and Kitaev, Sergey (2019) Polygoncircle and wordrepresentable graphs. Electronic Notes in Discrete Mathematics, 71. pp. 38. ISSN 15710653 (https://doi.org/10.1016/j.endm.2019.02.001)
Preview 
Text.
Filename: Enright_Kitaev_ENDM_2019_Polygon_circle_and_word_repeatable_graphs.pdf
Accepted Author Manuscript License: Download (228kB) Preview 
Abstract
We describe work on the relationship between the independentlystudied polygoncircle graphs and wordrepresentable graphs. A graph G = (V, E) is wordrepresentable if there exists a word w over the alphabet V such that letters x and y form a subword of the form xyxy ⋯ or yxyx ⋯ iff xy is an edge in E. Wordrepresentable graphs generalise several wellknown and wellstudied classes of graphs [S. Kitaev, A Comprehensive Introduction to the Theory of WordRepresentable Graphs, Lecture Notes in Computer Science 10396 (2017) 36–67; S. Kitaev, V. Lozin, “Words and Graphs” Springer, 2015]. It is known that any wordrepresentable graph is kwordrepresentable, 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 wordrepresentable is NPcomplete ([S. Kitaev, V. Lozin, “Words and Graphs” Springer, 2015, Theorem 4.2.15]). A polygoncircle graph (also known as a spider graph) is the intersection graph of a set of polygons inscribed in a circle [M. Koebe, On a new class of intersection graphs, Ann. Discrete Math. (1992) 141–143]. That is, two vertices of a graph are adjacent if their respective polygons have a nonempty 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 polygoncircle graph is NPcomplete [M. Pergel, Recognition of polygoncircle graphs and graphs of interval filaments is NPcomplete, GraphTheoretic Concepts in Computer Science: 33rd Int. Workshop, Lecture Notes in Computer Science, 4769 (2007) 238–247]. We show that neither of these two classes is included in the other one by showing that the wordrepresentable Petersen graph and crown graphs are not polygoncircle, while the nonwordrepresentable wheel graph W 5 is polygoncircle. We also provide a more refined result showing that for any k ≥ 3, there are kwordrepresentable graphs which are neither (k −1)wordrepresentable nor polygoncircle.
ORCID iDs
Enright, Jessica and Kitaev, Sergey ORCID: https://orcid.org/0000000333241647;

Item type: Article ID code: 67913 Dates: DateEvent20 March 2019Published5 March 2019AcceptedSubjects: Science > Mathematics > Electronic computers. Computer science Department: Faculty of Science > Computer and Information Sciences Depositing user: Pure Administrator Date deposited: 20 May 2019 07:51 Last modified: 27 Sep 2024 01:12 Related URLs: URI: https://strathprints.strath.ac.uk/id/eprint/67913