The numbers on the vertices give the order in which they were activated. Each state is labeled with a drawing of its active vertices, possibly with a yellow region that represents earlier inactive parts of the drawing that can no longer be modified.
#DRAW A FINITE STATE AUTOMATA AUTOMATA HOW TO#
On another level, the drawings within each state of the diagram show how to use this finite state machine to construct a drawing. So, this automaton recognizes only the graphs that have no forbidden configuration. But the only missing transitions are the ones that would create a six-vertex active set by a sequence of transitions that does not end in three consecutive right arrows (creating a \( K_6 \) in which one of the last three vertices has an earlier neighbor) or the ones that would exit a six-vertex active set by a sequence of transitions that does not begin with three consecutive left arrows (creating a \( K_6 \) in which one of the first three vertices has a later neighbor).
If a transition of either type does not exist in the diagram, it means that a step of that type will lead to an inescapable failure state. Every right-going transition is one that adds an active vertex, and every left-going transition is one that removes an active vertex. \( K_6 \) is 1-planar, but it has essentially only one drawing (modulo permutation of the vertices), and any example of this configuration would have a seventh vertex connected to four of the \( K_6 \) vertices, something that's not possible in a 1-planar drawing.Īt one level, the state diagram above can be viewed as a diagram for detecting this forbidden configuration. Some of our algorithms involved proving the existence of a finite set of forbidden configurations, and that idea works here, too: an indifference graph turns out to be 1-planar if and only if, for every \( K_6 \) subgraph, the first three vertices of the subgraph (in the activation order) have no later neighbors outside the subgraph, and the last three vertices have no other earlier neighbors. In a paper at WADS last year with Bannister and Cabello, we showed how to test 1-planarity for several special classes of graphs, but not for indifference graphs. These values are the input to the finite state machine. Thus, they can be represented by a sequence of binary values that specify whether the next step is to add or inactivate a vertex. Initialize an active set of vertices to be the empty set, and then perform a sequence of steps of two types: either add a new vertex to the active set and make it adjacent to all previous active vertices, or inactivate a vertex (removing it from the active set but not from the graph). Indifference graphs are the graphs that can be constructed by the following process. The diagram below describes a finite state machine that takes as input a description of an indifference graph, and produces as output a 1-planar drawing of it (that is, a drawing with each edge crossed at most once).