Polygoncircle and wordrepresentable graphs
Enright, Jessica and Kitaev, Sergey (2019) Polygoncircle and wordrepresentable graphs. Electronic Notes in Discrete Mathematics, 71. pp. 38. ISSN 15710653

Text (EnrightKitaevENDM2019Polygoncircleandwordrepeatablegraphs)
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.
Creators(s):  Enright, Jessica and Kitaev, Sergey ORCID: https://orcid.org/0000000333241647; 

Item type:  Article 
ID code:  67913 
Keywords:  Petersen graph, polygoncircle graph, wordrepresentable graph, circle graphs, computation, Electronic computers. Computer science, Discrete Mathematics and Combinatorics 
Subjects:  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:  06 Apr 2020 01:16 
Related URLs:  
URI:  https://strathprints.strath.ac.uk/id/eprint/67913 
Export data: 