Genus-Free Intersection Bounds for Embedded Graphs

Definitions and mathematical statement

Let $E(G)$ denote the edge set of a graph $G$, and write $m_i=|E(G_i)|$. The supplied registry asks whether two graphs embedded on a common surface can be redrawn so that their number of intersections is at most $O(m_1m_2)$, with an implied constant independent of the genus. However, the original excerpt begins in the middle of this conjectural bound and omits its hypotheses and the permitted redrawings. Consequently, the following is a conditional formulation of the intended quantifiers, not a recovered complete conjecture.

Once the input class and permitted redrawings have been specified, let $\mathcal A$ denote that class of triples $(S,\iota_1,\iota_2)$, where $\iota_i:G_i\hookrightarrow S$ is an embedding of a graph with finitely many edges. For $a\in\mathcal A$, let $\mathcal R(a)$ be the set of permitted pairs of redrawn embeddings, and let $I(r)$ be their intersection count under the intended counting convention. The proposed uniform bound would take the form \[ \exists C>0\;\forall a=(S,\iota_1,\iota_2)\in\mathcal A\;\exists r\in\mathcal R(a), \qquad I(r)\le C\,|E(G_1)|\,|E(G_2)|. \] Here $C$ is independent of the input, in particular of the genus of $S$. The finite-edge interpretation makes the asymptotic expression meaningful, but is not an explicitly recovered hypothesis. Neither $\mathcal A$, $\mathcal R$, nor the intersection convention is determined by the supplied excerpt. In particular, it does not specify orientability, compactness, boundary conditions, cellularity, connectedness, admissible graph types, or whether redrawings preserve the given embeddings up to isotopy, homeomorphism, or another equivalence. It also does not specify how shared vertices, tangencies, overlapping arcs, or multiple crossings at one point are treated. Thus the displayed formula records the intended uniform-bound pattern without supplying the missing mathematical scope.

The excerpt separately attributes a bound $O(gm_1m_2)$ for the general problem to Negami, reference [12]. This is a historical claim in the supplied source; the definition of $g$ and the hypotheses of that bound are not included.

As background, the excerpt reports a theorem obtained by the unnamed speaker with Niloufar Fuladi and Alfredo Hubard, reference [4]: a polynomial-time algorithm, given a graph cellularly embedded on a non-orientable surface, computes a non-orientable canonical system of loops of type $a_1a_1\cdots a_ga_g$, each loop intersecting each graph edge in at most $30$ points. A cellular embedding has complementary regions homeomorphic to open disks. The excerpt does not provide the complete surface, basepoint, intersection-counting, or computational conventions for this theorem. It describes the theorem as an analogue of the orientable theorem in reference [9]. This special algorithmic result must not be identified with the conjectural uniform bound for two graphs.

Short English statement

The intended question asks for a universal constant bounding intersections between two suitably redrawn embedded graphs by the product of their edge counts, independently of surface genus. The original excerpt omits the conjecture's hypotheses and permitted redrawings, so a complete precise conjecture cannot be recovered. The separately reported $30$-intersection theorem concerns canonical loops and does not supply the missing formulation.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30005371$, title "Genus-Free Intersection Bounds for Embedded Graphs," source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The record supplies the year $2023$ and no named proposer.
• Supplied report citation: Low-dimensional Topology (2023), Oberwolfach Reports, pp. 151--213, DOI 10.4171/owr/2023/3. Supplied source URL and literature_sources link labelled "original Oberwolfach report": https://doi.org/10.4171/owr/2023/3. This reference is supplied provenance; it was not independently accessed or verified for this draft.
• The supplied original excerpt attributes the historical $O(g|E(G_1)||E(G_2)|)$ bound to Negami [12], mentions related results [1] and [14], and attributes the non-orientable canonical-loop theorem to the unnamed speaker with Niloufar Fuladi and Alfredo Hubard [4], in comparison with an orientable theorem [9]. Bibliographic details for these numbered references are not supplied.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the problem open and describes the extracted text as an incomplete tail of a conjectural asymptotic bound, with the surrounding theorem addressing a special canonical-loop algorithm. This is supplied dated curation, not an independently verified literature assessment. The background explicitly requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified; its accompanying explanation limits verification to repairs of formula delimiters, notation, grammar, and typography. That label does not establish the missing mathematical hypotheses or verify the conjecture's current status.