The paper begins:
A continuous piecewise linear map ϕ : G → M is a weak embedding if, for every ε > 0, there is an embedding ψε : G → M with ||ϕ-ψε|| < ε.
The norm mentioned here is the uniform norm. The authors identify the challenge of recognizing a weak embedding as a combinatorial problem, and suggest a more efficient algorithm for its solution.
In the main section, the authors discuss the reconstruction and simplification of embeddings. For a graph G and an embedded graph H in an orientable surface, the main recognition algorithm starts with a piecewise linear simplicial map ϕ : G → H and then successively applies two newly introduced operations, namely clusterExpansion (Phase-1) and pipeExpansion (Phase-2), until it reports whether the simplicial map provided is a weak embedding. It is also established that the algorithm runs in O(mlogm) time.
After this, the authors discuss the process of “comput[ing] the combinatorial representation of an embedding ψϕ for the input ϕ.” Finally, the authors discuss how this algorithm “can be adapted to recognize weak embeddings ϕ : G → H when H is embedded in a nonorientable manifold.”
The authors’ approach is interesting and impressive, and the content and methodology are innovative and relevant. The graph-theoretical approach seems to be much more promising for the analysis of such combinatorial problems.
