Hypercube drawings with no long plane paths
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908867222306816 |
|---|---|
| author | Antić, Todor Fuladi, Niloufar Limbach, Anna Margarethe Valtr, Pavel |
| author_facet | Antić, Todor Fuladi, Niloufar Limbach, Anna Margarethe Valtr, Pavel |
| contents | We study the existence of plane substructures in drawings of the $d$-dimensional hypercube graph $Q_d$. We construct drawings of $Q_d$ which contain no plane subgraph with more than $2d-2$ edges, no plane path with more than $2d-3$ edges, and no plane matching of size more than $2d-4$. On the other hand, we prove that every rectilinear drawing of $Q_d$ with vertices in convex position contains a plane path of length $d$ (if $d$ is odd) or $d-1$ (if $d$ is even). We also prove that if a graph $G$ is a plane subgraph of every drawing of $Q_d$ for a sufficiently large $d$, then $G$ is necessarily a forest of caterpillars. Lastly, we give a short proof of a generalization of a result by Alpert et al. [Cong. Numerantium, 2009] on the maximum rectilinear crossing number of $Q_d$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_04665 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Hypercube drawings with no long plane paths Antić, Todor Fuladi, Niloufar Limbach, Anna Margarethe Valtr, Pavel Computational Geometry Combinatorics 05C10 (Primary) 68R10 (Secondary) G.2 We study the existence of plane substructures in drawings of the $d$-dimensional hypercube graph $Q_d$. We construct drawings of $Q_d$ which contain no plane subgraph with more than $2d-2$ edges, no plane path with more than $2d-3$ edges, and no plane matching of size more than $2d-4$. On the other hand, we prove that every rectilinear drawing of $Q_d$ with vertices in convex position contains a plane path of length $d$ (if $d$ is odd) or $d-1$ (if $d$ is even). We also prove that if a graph $G$ is a plane subgraph of every drawing of $Q_d$ for a sufficiently large $d$, then $G$ is necessarily a forest of caterpillars. Lastly, we give a short proof of a generalization of a result by Alpert et al. [Cong. Numerantium, 2009] on the maximum rectilinear crossing number of $Q_d$. |
| title | Hypercube drawings with no long plane paths |
| topic | Computational Geometry Combinatorics 05C10 (Primary) 68R10 (Secondary) G.2 |
| url | https://arxiv.org/abs/2603.04665 |