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.
to work with word-representability of graphs was created by Haoran
Sun in 2021, and it is based on the notion of a semi-transitive
orientation. A unique feature of this software, compared to that
created by Marc Glen RepresentableGraphs.jar
(see description here),
is that it is capable of producing automatically human-verifiable
proofs of non-word-representability (recognising word-representable
graphs in an NP-complete poblem). We refer to the paper "Human-verifiable
proofs in the theory of word-representable graphs" for a
description of the proof format.
The software 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. A graph can be partially
oriented, which is achieved by switching between "oriented"
and "non-oriented" buttons. The "Add" and "Subtract" buttons
increase and decrease the size of the matrix, respectively (that is,
removes the highest vertex, or adds a new one). The "Clear" button
removes all edges from the current graph. The "Clear Orientation"
button removes orientation of all edges in the current graph.
Checking for word-representability
The button "Test" checks whether the given fully-oriented graph is
semi-transitively oriented, or whether the given partically orinted
graph admits extension of the orientation to semi-transitive one, or
whether the given undirected graph admits a semi-transitive
orientation. "Test (Smart Version)" has the same functionality as
"Test" but uses a more advanced algorithm (Algorithm 2 in the paper
"Human-verifiable proofs in the theory of word-representable
graphs"). If the graph in question is not word-representable, a pop
out window will offer to print a proof of this fact. Such a proof
can be used in a research paper to justify non-word-representability
of a graph. The time used to find the proof will be printed at the
end of the proof. We note that a proof of non-extendability of a
partially oriented graph to a semi-transitively oriented graph is a
useful feature: when strating from an undirected graph, one can
notice symmetries allowing assumptions on orientation of certain
edges without loss of generality. Such assumptions can allow finding
a semi-transitive orientation quicker, or reduce the length of a
non-word-representability proof dramatically.