Word-representable graphs

A graph G = (V, E) is word-representable if there exists a word w over V such that x and y alternate in w if and only if (x,y) is in E. A comprehensive introduction to the theory of word-representable graphs is given in the book "Words and Graphs" by Sergey Kitaev and Vadim Lozin published by Springer. Also, see "A Comprehensive Introduction to the Theory of Word-Representable Graphs" by Kitaev published in the Lecture Notes in Computer Science 10396. Moreover, see the wiki page giving basic information on the theory and its generalizations. A key result in the theory of word-representable graphs is the theorem stating that a graph is word-representable if and only if it admits a semi-transitive orientation.

The user-friendly program


to work with word-representability of graphs, that requires Java version 7 or higher, was written by Marc Glen in 2014-15, and it is based on the notion of a semi-transitive orientation. This program presents a graph in matrix form on the left, and in graphical form on the right. Edges are added/removed by clicking on the appropriate entry in the matrix. The program presents the following functionality:

Manipulating the graph

Controls for manipulating the graph are on the left-hand side panel. There is an "oriented/non-oriented" pair of radio buttons, which toggles which type of edge is placed on the graph. The up and down arrows decrease and increase the size of the matrix respectively (that is, removes the highest vertex, or adds a new one). The "clear" button completely removes all edges from the current graph.

Checking for word-representability

Controls for checking the word-representability of a graph are at the bottom of the window. The button "Is this orientation semi-transitive?" checks whether the given fully-oriented graph is semi-transitively oriented. The button "Is this graph word-representable?" checks whether a given (non-oriented) graph is word-representable, and if it is, it outputs a semi-transitive orientation of the graph, and a uniform word representing it. If you orient some (but not all) edges before clicking the button, these will be used as clues for what kind of orientation a semi-transitive orientation may be. So for example, if you orient one particular edge in one way, the program will not check any of the oriented graphs where that edge was oriented the other way, when searching for a semi-transitive orientation. The button "Get word representing this graph" will show a uniform word representing the current graph, if the graph is indeed word-representable, and will allow the user to save that word to a file.

Menu bar

File menu

New - loads a graph with no edges and the current number of vertices

Load - loads a saved graph

Save - saves the current graph

Quit - quits the application

Word menu

Load graph from word - accepts a word as input and loads a graph that the word represents.

Check if word represents this graph - accepts a word as input and checks whether that word represents the current graph.

Get uniform word from word - accepts a word as input and outputs a uniform word representing the same graph.