# Recognition algorithms for subfamilies of threshold graphs

Here's one possible answer to Sergio's question, about nontrivial families of graphs within which testing 1-planarity is polynomial: it's possible to test whether a threshold graph is 1-planar in linear time.

But maybe this is cheating, because it has very little to do with 1-planarity. The more general result is: let \( F \) be any family of graphs closed under induced subgraphs. Then it's possible to test whether a threshold graph belongs to \( F \) in linear time.

This follows from two known facts. First, any formal language (over a finite alphabet) that is closed under subsequence operations can be characterized by a finite set of forbidden subsequences (e.g. see Gasarch's survey on recursive combinatorics, in the sentence about "another interesting example"). Therefore, any such language is regular. And secondly, every \( n \)-vertex threshold graph may be represented by an \( (n-1) \)-bit binary string, where the 0's represent the operation of adding an isolated vertex and the 1's represent the operation of adding a vertex connected to all the others; in this representation, induced subgraphs correspond to subsequences and vice versa. So if \( F \) is a family of graphs closed under induced subgraphs, then the set of binary strings corresponding to threshold graphs in \( F \) will be closed under subsequences and therefore will be a regular language.

So all we need to do to test whether a threshold graph \( G \) is 1-planar is to convert \( G \) to its binary sequence and then test whether that sequence belongs to a certain regular language derived from the finite set of minimally non-1-planar threshold graphs (whatever they happen to be).