Simultaneous Embeddings of Random Planar Graphs

Definitions and mathematical statement

For each integer $n\geq 4$, let $V_n=\{v_1,\ldots,v_n\}$. Define $\mathcal T_n$ to be the family of labeled stacked triangulations constructed from the complete graph $K_4$ on $v_1,\ldots,v_4$ as follows. For each $i=4,\ldots,n-1$, choose one triangular face of the current triangulation, insert $v_{i+1}$ into that face, and join it to the three vertices bounding that face. Faces are understood combinatorially on the sphere: there are $2i-4$ faces at this stage. In a plane representation this count includes the unbounded face. Members of $\mathcal T_n$ are the resulting labeled graphs.

For a graph $G$ on $V_n$ and a set $P\subset{\mathbb{R}}^2$ of $n$ distinct points, a crossing-free straight-line embedding of $G$ on $P$ is a bijection $\phi:V_n\to P$ such that each edge $uv$ is represented by the segment $[\phi(u),\phi(v)]$, no vertex image lies in the relative interior of an edge segment, and distinct edge segments intersect only at the image of a common endpoint, if they have one.

Let $G_1,G_2$ be independent random graphs, each uniformly distributed on $\mathcal T_n$. Define \[ p_n=\Pr\!\left(\begin{array}{l} \text{there exists }P\subset{\mathbb{R}}^2,\ |P|=n,\text{ such that both }G_1\text{ and }G_2\\ \text{have crossing-free straight-line embeddings on }P \end{array}\right). \] The two embeddings may use different bijections $\phi_1,\phi_2:V_n\to P$; equally labeled vertices are not required to occupy the same point. Crossing-freeness is required separately for each drawing, with no restriction on intersections between edges from different drawings. No general-position restriction on $P$ is imposed in the supplied reconstructed statement.

Determine the asymptotic behavior of $p_n$ as $n\to\infty$, including its limit if one exists. The source asks for the probability "for large $n$" without specifying a desired asymptotic precision. The distribution and common-point-set formulation above follow the supplied reconstructed statement; the supplied original excerpt refers instead to the distribution in the proofs of Theorems 1 and 2 without reproducing its definition. Those conventions require source review. The registry labels this problem open and the reconstruction corrected_verified; these are supplied curation labels, not independent verification.

Short English statement

Independently choose two uniformly random labeled stacked triangulations on $n$ vertices from the supplied construction. How does the probability that both can be drawn with straight edges and no crossings on one common set of $n$ plane points behave as $n\to\infty$? Each graph may assign its vertices to those points differently.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30005805$, title Simultaneous Embeddings of Random Planar Graphs, exact source problem code catalogue entry. The record attributes the problem to the Oberwolfach Reports Open Problems collection and gives proposed year 2024; no individual proposer is supplied.
• Discrete Geometry (2024), Oberwolfach Reports, pp. 137--202, DOI 10.4171/owr/2024/3. Supplied report reference and literature source: https://doi.org/10.4171/owr/2024/3. The retained original passage asks about simultaneous embeddings for two independent graphs from the distribution used in the proofs of Theorems 1 and 2, and mentions its relevance to Problem 1 without supplying that problem.
• A Logarithmic Bound for Simultaneous Embeddings of Planar Graphs. Supplied literature source: https://doi.org/10.1007/s00454-024-00665-7.
• Literature assessment dated exactly 2026-08-22: supplied dated curation, not independently verified. It labels the problem open, identifies the two-random-graph question as Problem 6.1 of the 2024 primary paper, and reports a non-embeddability result for about $3\log_2(n)$ independent stacked triangulations, rather than the requested two-graph limit. The record also states that its reconstruction was checked against the official Oberwolfach report; that verification claim is supplied metadata and has not been independently checked here.