Define a graph as the tuple:
$(V,C)$ where
$V$ is the set of all verticies in the graph and
$C=\{(a,b)|a,b\in V\}$ is the set of curves that connects some or all of the verticies.
Is it true that all such graph can be drawn on a 2D plane in such way that no 2 curve cross each other?
I tried Bing search, queried Computer Science SE and here, and even entered the title into the asking box, but no relevant post turned up, so I'm posting a question. I'm from Web application programming background, and is unfamiliar with advanced maths.
It isn't hard to see that not all graphs are planar. The complete graph on five vertices is not (the complete graph has an edge connecting every pair of vertices). Choose any four points in the plane to serve as four of the vertices, and connect them with curves. The result can be manipulated continuously without any edges intersecting or passing through vertices to look like this:
There are four regions in which the fifth vertex may be placed. If it is placed in any of the three inner triangles, there is no way to connect this vertex to the vertex outside that triangle without crossing one of the three sides. Similarly, if you place the fifth vertex outside the large triangle, you cannot connect it to the center vertex.
On the other hand, you can embed any finite graph as points and curves in 3-dimensional space.