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

finite state machine for recognizing 1-planar indifference graphs

Indifference graphs are the graphs that can be constructed by the following process. 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). Thus, they can be represented by a sequence of binary values that specify whether the next step is to add or inactivate a vertex. These values are the input to the finite state machine.

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

At one level, the state diagram above can be viewed as a diagram for detecting this forbidden configuration. Every right-going transition is one that adds an active vertex, and every left-going transition is one that removes an active vertex. 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. 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). So, this automaton recognizes only the graphs that have no forbidden configuration.

On another level, the drawings within each state of the diagram show how to use this finite state machine to construct a drawing. 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. The numbers on the vertices give the order in which they were activated. For each left transition, it is always possible to remove the oldest active vertex from the drawing and replace the parts of the drawing surrounding it by a yellow region to create a drawing that matches the new state. Similarly, for each right transition, it is always possible to add one more active vertex to the drawing, connect it to the other active vertices, and then simplify some parts of the drawing to yellow regions, again creating a drawing that matches the new state. Therefore, every graph that can be recognized by this state diagram has a 1-planar drawing.

Since the machine described by the diagram finds a drawing for a given indifference graph if and only if the graph has no forbidden configurations, it follows that these forbidden configurations are the only ones we need to describe the 1-planar graphs and that this machine correctly finds a 1-planar drawing for every indifference graph that has one. This same technique doesn't always generalize: A result from my WADS paper that it's NP-complete to test 1-planarity for graphs of bounded bandwidth shows that, even when a class of graphs can be represented by strings of symbols from a finite alphabet it's not always going to be possible to find a finite state machine to test 1-planarity. But it would be interesting to find more graph classes for which the same simple technique works.

(G+)