{"id":"arxiv/2603.04665","url":"https://arxiv.org/abs/2603.04665","tags":["cs.CG","math.CO"],"score":0,"title":"Hypercube drawings with no long plane paths","domain":"cs.CG","source":"arxiv","authors":["Todor Antić","Niloufar Fuladi","Anna Margarethe Limbach","Pavel Valtr"],"reviews":0,"subject":"cs.CG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-03-04","reactions":{}}