Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.19274 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914833014718464 |
|---|---|
| author | Chakraborty, Sutanoya Ghosh, Arijit |
| author_facet | Chakraborty, Sutanoya Ghosh, Arijit |
| contents | 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-Štefankovič, about drawing graphs on surfaces, and derive the Loebl-Masbaum theorem from it. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_19274 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Hanani-Tutte Theorem for Cycles Chakraborty, Sutanoya Ghosh, Arijit Combinatorics 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-Štefankovič, about drawing graphs on surfaces, and derive the Loebl-Masbaum theorem from it. |
| title | A Hanani-Tutte Theorem for Cycles |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2405.19274 |