If $X$ is a topological space, write $C_n(X)$ for the configuration space of distinct ordered tuples of points in $X$: $$C_n(X) = \{(x_1, \ldots, x_n) \in X^n \mbox{ so that $i \neq j \implies x_i \neq x_j$ } \}.$$ Define the banana graph $\beta_k$ to be the suspension of the discrete space $\{1, \ldots, k\}$. Finally, write $\Sigma_g$ for the closed orientable surface of genus $g$.

A) If $X = \beta_4$ is the four-edge banana graph, is there a homotopy equivalence $C_3(X) \simeq \Sigma_{13}$?

As background, the thesis of Aaron Abrams (available on his website http://home.wlu.edu/~abramsa/publications/index.html) gives homotopy equivalences

$$ \begin{align*} C_2(K_5) & \simeq \Sigma_6 \\ C_2(K_{3,3}) & \simeq \Sigma_4. \end{align*} $$ Abrams also proves that a related combinatorial approximation of configuration space $C_n^{approx}(X)$ satisfies $$ \begin{align*} C_3^{approx}(K_5) & \simeq \Sigma_{16} \\ C_4^{approx}(K_{3,3}) & \simeq \Sigma_{37}, \end{align*} $$ where $K_5$ is a complete graph and $K_{3,3}$ is complete bipartite. (Thank you to user j.c. for pointing out the difference between $C_n^{approx}$ and $C_n$, which I had not understood.) So this sort of thing has happened before!

Also, using an explicit simplicial model of $C_3(\beta_4)$ that Sage tells me has 336 vertices and 840 facets, I am able to compute that $$ H^*(C_3(\beta_4) \, ; \mathbb{Z}) \simeq H^*(\Sigma_{13} \, ; \mathbb{Z}), $$ and that the cup product in rational cohomology gives a non-degenerate pairing on $H^1$.

B) How might I check if a finite simplicial complex has the homotopy type of some $\Sigma_g$?

I say "might" because it's probably not computable in general. Finally, I'll ask what might be a tricky question:

C) For what graphs $G$ and $n \in \mathbb{N}$ does $C_n(G)$ have the homotopy type of a surface?

At Ryan Budney's suggestion, I have collapsed many free faces. (The algorithm I used comes from the paper https://arxiv.org/pdf/1303.6422.pdf by Benedetti and Lutz). The result is a complex with 120 vertices and 288 facets. It is a pseudomanifold! Sage computes a presentation for $\pi_1$ $$ \langle a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z \rangle / \langle \omega \rangle $$ where $\omega$ is the impressive-looking word $$ y^{-1}a^{-1}bf^{-1}en^{-1}ml^{-1}x^{-1}wo^{-1}vkg^{-1}hpu^{-1}tdh^{-1}ic^{-1}e^{-1}car^{-1}qlod^{-1}fq^{-1}i^{-1}s^{-1}b^{-1}xt^{-1}m^{-1}p^{-1}rsk^{-1}uznjv^{-1}w^{-1}yz^{-1}j^{-1}g $$ in which every variable appears exactly twice, once with an inverse. So $\pi_1$ is also correct!

findit, the software Magnus (available for some linux systems) is very versatile and powerful. There is probably other sortware out there, but that's where I would start. $\endgroup$ – Ryan Budney May 4 '17 at 21:48