1
$\begingroup$

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.

  • 2
    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.2012-02-07
  • 0
    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!!2012-02-07
  • 0
    A piece of paper is usually considered _two_-dimensional. The definition you give sounds like that of a [planar graph](http://en.wikipedia.org/wiki/Planar_graph). Is that what you mean, or is it something else?2012-02-07
  • 0
    Yes you are right!planar or non planar graph.2012-02-07

1 Answers 1