# Polygon-circle and word-representable graphs

Enright, Jessica and Kitaev, Sergey
(2019)
*Polygon-circle and word-representable graphs.*
Electronic Notes in Discrete Mathematics, 71.
pp. 3-8.
ISSN 1571-0653

Text (Enright-Kitaev-ENDM-2019-Polygon-circle-and-word-repeatable-graphs)
Enright_Kitaev_ENDM_2019_Polygon_circle_and_word_repeatable_graphs.pdf Accepted Author Manuscript Restricted to Repository staff only until 20 March 2020. License: Download (228kB) | Request a copy from the Strathclyde author |

## Abstract

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 ⋯ iff xy is an edge in E. Word-representable graphs generalise several well-known and well-studied classes of graphs [S. Kitaev, A Comprehensive Introduction to the Theory of Word-Representable Graphs, Lecture Notes in Computer Science 10396 (2017) 36–67; S. Kitaev, V. Lozin, “Words and Graphs” Springer, 2015]. 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 ([S. Kitaev, V. Lozin, “Words and Graphs” Springer, 2015, 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 [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 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 [M. Pergel, Recognition of polygon-circle graphs and graphs of interval filaments is NP-complete, Graph-Theoretic 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 word-representable Petersen graph and crown graphs are not polygon-circle, while the non-word-representable wheel graph W 5 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.

Author(s): | Enright, Jessica and Kitaev, Sergey ORCID: https://orcid.org/0000-0003-3324-1647 |
---|---|

Item type: | Article |

ID code: | 67913 |

Keywords: | Petersen graph, polygon-circle graph, word-representable 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: | 12 Nov 2019 02:58 |

Related URLs: | |

URI: | https://strathprints.strath.ac.uk/id/eprint/67913 |

Export data: |