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 RepresentableGraphs.jar to work with word-representability of graphs, that requires Java version 7 or higher, was written by me 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. |