Is "Recognizing" 1-planar graphs the same as "Generating" them?

Question

I'm currently doing research in the field of recognizing 1-planar graphs, which is proven to be efficient for certain subclasses e.g. optimal or outer 1-planar graphs. During my research, I came across a paper by Brandenburg ("Recognizing Optimal 1-Planar Graphs in Linear Time") and a paper by Auer et. al. ("Recognizing Outer 1-Planar Graphs in Linear Time"). Auer et. al. developed an algorithm for recognizing outer 1-planar graphs using SPQR-Trees. Brandenburg developed an algorithm for recognizing optimal 1-planar graphs using a graph reduction system. However, neither of them generates graphs of the given subclass and I'm wondering if the efficient recognition of optimal or outer 1-planar graphs means that generating them can also be efficiently done. I haven't found any algorithms covering my interest.

Answer 1

For the case of optimal $1$-planar graphs, the paper by Brinkmann et al. "Generation of simple quadrangulations of the sphere" seems to do what you want: as observed in the Brandenburg paper, all the optimal $1$-planar graphs are obtained from the $3$-connected quadrangulations by adding two crossing edges inside each quadrilateral.

For the case of outer-$1$-planar graphs, I suppose that you could reverse the SPQR-tree algorithm: generate all possible tree structures, then fill in the nodes in all possible ways by the subgraphs that are allowed in the outer-$1$-planar case. I don't have a good sense of how efficient this is.