Is it possible to check, whether graph contains K_5 as a sub-graph in linear time? (There obviously exists an algorithm to check whether graph contains K_5 OR K_3_3, but what about K_5 only?).
A more general question, is it possible to check whether graph G(V, E), contains some other sub-graph G2(V2, E2) in a way, that will be linear depending on E (or at least polynomial) (probably exponential or even worse depending depending on E2) (e. g. wрether there is an algorithm that solves this problem in something like O((E ^ k) * A(E2, E2)) for fixed k?
I don't think so. The k-Clique problem is W[1] — hard. That means that there's a very high chance it doesn't admit an FPT algorithm. An FPT algorithm gives the running time of $$$O(n^{c}*f(k))$$$ where $$$c$$$ is a constant, $$$n$$$ is the size of the original graph $$$G$$$ and $$$k$$$ is the size of the clique you want to find in $$$G$$$.
What do you mean by „containing”? I can understand is as „there are five vertices in G and every two of them are connected with edge” or „there is a subgraph isomorphic with clique of 5 vertices”.
You are misunderstanding between subgraph and minor graph. The theorem about planer graph is for graph minor, not subgraph. So, linear-time algorithm for planarity cannot be used.
By the way, I don't think such an algorithm exists, as Mindjolt pointed out (but still a bit ambiguous). We have no linear-time algorithm even for triangle detection.