simplicial complex into ${\mathbb R}^n$, which is a natural generalization of graph planarity, was studied in [@MatousekTancerWagner:HardnessEmbeddings-2011]. Theorem \[t:emb-metast\] clarifies the decidability of this problem for $k\le \frac23 n-1$; this is the so-called *metastable range* of dimensions, which was left open in [@MatousekTancerWagner:HardnessEmbeddings-2011]. Briefly, in the metastable range, the classical theorem of Weber (see [@Weber:PlongementsPolyedresDomaineMetastable-1967]) asserts that embeddability is equivalent to the existence of a ${{\mathbb Z}}_2$-equivariant map $(K\times K)\smallsetminus \Delta_K \to S^{{{n}}-1}$ whose domain is equivariantly homotopy equivalent to a finite simplicial complex[^8] with a free simplicial action of ${{\mathbb Z}}_2$. Thus, Theorem \[t:emb-metast\] follows immediately from Theorem \[theorem:equivariant\]; we refer to [@MatousekTancerWagner:HardnessEmbeddings-2011] for details.

Polynomial running times {#polynomial-running-times .unnumbered}
------------------------

We remark that for fixed $G$ and ${{d}}$, the algorithms of Theorems \[theorem:equivariant\] and \[thm:main\_theorem\] run in polynomial time. The algorithm of Theorem \[t:emb-metast\] also runs in polynomial time when the dimension $n$ is fixed. These claims are proved in an extended version of this paper, [@aslep-long].

Outline of the proof {#outline-of-the-proof .unnumbered}
--------------------

In the rest of this section we sketch the main ideas and tools needed for the algorithm of Theorem \[thm:main\_theorem\]. Even though the computation is very similar in its nature to that of [@CKMSVW11], 