|
5 | added another characterization | ||
|
Another (less known) characterization of planar graphs is Schnyder's theorem, which characterizes planar graphs according to order dimension. That is, a graph is planar if and only if its incidence poset has order dimension at most 3. Also, I would be remiss to not mention the beautiful (strong) Hanani-Tutte theorem: A graph is planar if and only if it has a drawing in the plane such that every two non-adjacent edges cross an even number of times. |
||||
|
|
4 | added 51 characters in body | ||
|
Another (less known) characterization of planar graphs is Schnyder's theorem, which characterizes planar graphs according to order dimension. That is, a graph is planar if and only if its incidence poset has order dimension at most 3. |
||||
|
|
3 | deleted 52 characters in body | ||
|
Another (less known) characterization of planar graphs is Schnyder's theorem http://en.wikipedia.org/wiki/Schnyder's_theorem, which characterizes planar graphs according to order dimension. That is, a graph is planar if and only if its incidence poset has order dimension at most 3. |
||||
|
2 | deleted 48 characters in body; deleted 1 characters in body | ||
|
|
1 |
|
||
