A Hanani-Tutte Theorem for Cycles
| Autor: | Chakraborty, Sutanoya, Ghosh, Arijit |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Given a drawing $D$ of a graph $G$, we define the crossing number between any two cycles $C_{1}$ and $C_{2}$ in $D$ to be the number of crossings that involve at least one edge from each of $C_1$ and $C_2$ except the crossings between edges that are common to both cycles. We show that if the crossing number between every two cycles in $G$ is even in a drawing of $G$ on the plane, then there is a planar drawing of $G$. This result can be extended to arbitrary surfaces. We also establish an equivalence between our result and a fundamental result due to Cairns-Nikolayevsky and Pelsmajer-Schaefer-\v{S}tefankovi\v{c}, about drawing graphs on surfaces, and derive the Loebl-Masbaum theorem from it. Comment: Included equivalence with an established result, and derived a previous theorem from the result |
| Databáze: | arXiv |
| Externí odkaz: |
|