Removing even crossings on surfaces (Q1039443): Difference between revisions

The Hanani-Tutte theorem states that every drawing on the plane of a non-planar graph contains two non-adjacent edges which cross an odd number of times. The paper investigates the extension of this result to arbitrary surfaces. \newline The first result states that if a graph \(G\) can be drawn on a surface \(S\) so that all its edges are even, then \(G\) can be embedded in \(S\). Moreover, if \(D\) is a drawing of \(G\) on \(S\) and \(E_0\) is the set of even edges in \(D\), then \(G\) can be drawn on \(S\) so that no edge in \(E_0\) is involved in any crossing. \newline A generalized thrackle is a graph that can be drawn so that any pair of edges intersect an odd number of times (counting endpoints). Besides providing a simpler, topological proof of the theorem stating that a bipartite graph \(G\) is a generalized thrackle if and only if \(G\) can be embedded in that surface, the authors prove also that a graph \(G\) is a generalized thrackle on a surface \(S\) if and only if \(G\) has an X-parity embedding in the surface obtained by adding a crosscap X to \(S\), with the same embedding scheme. \newline Finally, if one denotes by \(cr_s(G)\) the crossing number of a graph \(G\) on a surface \(S\) and by \(ocr_s(G)\) the odd crossing number of \(G\) on \(S\), then the next statements hold. {\parindent=5mm \begin{itemize}\item[1.]For any surface \(S\), \(cr_S(G) \leq 2ocr_S(G)^2\). \item[2.]If \(G\) is a graph on a surface \(S\) with \(ocr_S(G) \leq 2\), then \(ocr_S(G) = cr_S(G)\). \end{itemize}}