Randomly planar graphs (Q1377765)

A graph \(G\) is randomly planar if every planar embedding of every connected subgraph \(H\) of \(G\) can be extended to a planar embedding of \(G\). Intuitively, a graph is randomly planar if a planar embedding of it can be built up in any manner whatsoever. A graph is planar-forbidden if it is the union of a cycle and a path of length at least three between two (possibly equal) vertices of the cycle. In this paper the authors show that a graph is randomly planar if and only if it contains no planar-forbidden subgraphs. They go on to show such graphs are exactly those where every edge-block is isomorphic to \(K_1\), \(C_n\), \(K_4\), \(K_{2,n}\) with \(n \geq 3 \), or \(K_{1,1,n}\) with \(n \geq 2\). They give a similar theorem for strongly randomly planar graphs, which are defined the same as randomly planar graphs except for the extra condition that embeddings of disconnected subgraphs \(H\) must also extend to embeddings of \(G\).