Suppose that we are given a finite connected graph, i.e. the finite vertex set $V$ and a finite edge set $E\subseteq P(V)$.
Is there an algorithm to find the Euler characteristic of any cellular embedding of our graph?
Recently I learned that it is not easy to find the "faces" if we are only given the vertex set and the edge set. We need to find an embedding into a compact connected surface in a such a way that the complement of the image of the graph is homeomorphic to a disjoint union of open discs (this type of embedding is called cellular, sometimes people also call it just a "map". The connected component of the complement of the image of graph gives us the faces). I am curious how one could find the Euler characteristic of our surface and therefore our surface (up to homeomorphism).
I suppose that after this edit it should be obvious to anybody, why this is NOT a duplicate.
Rather than speaking of the Euler characteristic of a graph, we traditionally speak of the genus of a graph, which is the least genus of a surface into which it can be embedded...
...but there is no way to find this number that improves substantially on finding all embeddings of the graph.
This CS StackExchange answer outlines a method. The basic idea is that the global structure of the embedding is determined by some local decisions: for each vertex, you should determine the cyclic order of the edges out of that vertex.
Not all choices made at the different vertices are compatible, so we work out the ones that are, and now we can work out the faces of this embedding and determine the genus (or, if you prefer, the Euler characteristic). If we do this for all possible ways to choose the cyclic orders, we can get a bunch of embeddings, and then we can choose the best one.
There are better algorithms, and there are ways to speed up this algorithm so we don't have to check very possibility, but there's no fast algorithm. See Wikipedia for some citations.