# Graph, planar or not?

A graph $L_n$ has vertices $V=\{l_1,l_2,\dotsc,l_n\}\cup\{r_1,r_2,\dotsc,r_n\}$ and edges $E=\{(l_i,r_j): i \ge j\}$ .

Which of these graphs $L_1$, $L_2$, etc. are planar and which are not? For those that are planar, give an appropriate depiction (scheme) and for the others write the proof.

-
Could you give a brief definition of what a one-dimensional graph is? If I've guessed the definition right, I think you'll find that $L_1$ and $L_2$ are one-dimensional and the rest are not, but it would help to know exactly which definition you're using. –  Ilmari Karonen Feb 7 '12 at 14:43
By one-dimensional I mean a graph that can be depicted on a piece of paper and the edges do not meet.Thanks for your time!! –  thrasos Feb 7 '12 at 15:01
A piece of paper is usually considered two-dimensional. The definition you give sounds like that of a planar graph. Is that what you mean, or is it something else? –  Ilmari Karonen Feb 7 '12 at 15:08
Yes you are right!planar or non planar graph. –  thrasos Feb 7 '12 at 16:13

In your case, $L_i$ is a subgraph of $L_j$ for all $j > i$; thus, if we can show that $L_i$ is non-planar for some $i$, we've also shown it for all $j > i$. Conversely, showing that $L_i$ is planar implies that $L_j$ is also planar for all $j < i$.
It should not be particularly hard to draw the graphs from $L_1$ up to $L_4$ on paper without intersections, thereby demonstrating that they're planar.
As for $L_5$, recall Wagner's theorem: A finite graph is planar if and only if it does not have $K_5$ (the complete graph on five vertices) or $K_{3,3}$ (the complete bipartite graph on six vertices) as a minor. Can you find either of these graphs as a minor in $L_5$? (Hint: try contracting edges of the form $(l_i, r_i)$.)
Or note that each of $\ell_3,\ell_4,\ell_5$ is adjacent to each of $r_1,r_2,r_3$. –  Gerry Myerson Feb 7 '12 at 23:23