Can any non-planar graph with n minimum crossing points be 'drawn' on a sphere so the vertice and edge sets are the same and it has a connected subset A with minimum r crossing points and a disjoint connected subset B with minimum s crossing points where r+s=n? And other subsets can be found for any value r such that 1 < r < n ?
1
-
$\begingroup$ I downvoted the question because it is definitely not research level; further I miss some clarification, what kind of graphs and transformation you have in mind. A planar graph and the embedding of a graph in the euclidean plane are different things; so do you actually have geometric embeddings in mind? $\endgroup$– Manfred WeisCommented Apr 26, 2014 at 10:35
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
No. Suppose it could, then you could just apply the steriographic projection from an interior point of some face on the sphere and obtain a graph on the plane with no crossing edges that is isomorphic to yours. Hence your graph must have been planar.
answered Apr 26, 2014 at 7:00
-
$\begingroup$ Could a non-planar graph be 'translated' from a plane to a torus or some other surface in 3-D space and have no crossing points? $\endgroup$ Commented Apr 26, 2014 at 7:07
-
1$\begingroup$ This is obvious, isn't it? Make you graph thick (ribbon graph) and patch the holes. Wrong question for this site. $\endgroup$ Commented Apr 26, 2014 at 9:13
-
$\begingroup$ It is not completely obvious to me though that you will actualy end up with a surface after using your patching procedure. $\endgroup$ Commented Apr 28, 2014 at 19:27
$\begingroup$
$\endgroup$
No, it has the wrong graph genus.
answered Apr 26, 2014 at 7:16