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. 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.
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.
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
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.