Let $G_n$ be the simple graph with the set of vertices $V_n=\{1, 2, . . . , n\}$. Two different vertices $x$ and $y$ are adjacent if $x$ is a multiple of $y$ or $y$ is a multiple of $x$. For what $n$ is $G_n$ planar?
I tried to draw graph starting from small $n$ until I cannot draw graph $G_n$ it without crossings. When that happens, moving some of the vertices so I can avoid the crossings. But I cannot find which $n$ is $G_n$ graph planar?
Any hint is highly appreciated.
If $n\geq18$ the graph $G_n$ is not planar since the vertices $\{1,2,3,6,12,18\}$ are the vertices of a $K_{3,3}$ inside $G_n$.