Blocking nonorientability of a surface
A collection of pairwise noncrossing simple closed curves in a nonorientable surface \(S\) is a blockage if every one-sided simple closed curve in \(S\) crosses at least one of them. \textit{N. Robertson} and \textit{R. Thomas} [J. Graph Theory 15, 407-419 (1991; Zbl 0735.05031)] conjectured that the orientable genus of any graph \(G\) imbedded in \(S\) with sufficiently large face width is ``roughly equal to one-half of the minimum number of intersections of a blockage with the graph. \textit{B. Mohar} [Discrete Math. 182, 245-253 (1998; Zbl 0889.05040)] disproved that conjecture, and made is revised one. In the present paper, the authors show that the two conjectures hold up to a constant error term: For any graph \(G\) imbedded in \(S\), the orientable genus of \(G\) differs from the conjectured value by at most \(O(g^2)\), where \(S\) has genus \(g\).
- Combinatorial Local Planarity and the Width of Graph Embeddings
- Computing the orientable genus of projective graphs
- Generating locally-cyclic triangulations of surfaces
- Graph theory
- Graphs on surfaces
- scientific article; zbMATH DE number 3188197 (Why is no real title available?)
- On the orientable genus of graphs embedded in the klein bottle
- On the orientable genus of graphs with bounded nonorientable genus
- The graph genus problem is NP-complete
- Uniqueness and minimality of large face-width embeddings of graphs
This page was built for publication: Blocking nonorientability of a surface
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1403908)
