Blocking nonorientability of a surface
type: Item
instance of: scholarly article
title: Blocking nonorientability of a surface
zbMATH Open document ID: 1026.05031
DOI: 10.1016/S0095-8956(02)00025-4
author: Bojan Mohar
author: Alexander Schrijver
published in: Journal of Combinatorial Theory. Series B
publication date: 2003-08-20T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 1967935
zbMATH Keywords: blockage
zbMATH Keywords: closed curve
zbMATH Keywords: genus
reviewed by: Arthur T. White
MaRDI profile type: Publication
cites work: Q5724434
cites work: Q5422499
cites work: Computing the orientable genus of projective graphs
cites work: Generating locally-cyclic triangulations of surfaces
cites work: Combinatorial Local Planarity and the Width of Graph Embeddings
cites work: Uniqueness and minimality of large face-width embeddings of graphs
cites work: On the orientable genus of graphs with bounded nonorientable genus
cites work: Graphs on surfaces
cites work: On the orientable genus of graphs embedded in the klein bottle
cites work: The graph genus problem is NP-complete
description: scientific article; zbMATH DE number 1967935