Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Recognizing weak embeddings of graphs
Akitaya H., Fulek R., Tóth C.  ACM Transactions on Algorithms 15 (4): 1-27, 2019. Type: Article
Date Reviewed: Mar 12 2021

The paper begins:

A continuous piecewise linear map ϕ : GM is a weak embedding if, for every ε > 0, there is an embedding ψε : GM 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 ϕ : GH 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 ϕ : GH 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.

Reviewer:  Sudev Naduvath Review #: CR147212 (2106-0159)
Bookmark and Share
Graph Theory (G.2.2 )
Computational Geometry And Object Modeling (I.3.5 )
Discrete Mathematics (G.2 )
Would you recommend this review?
Other reviews under "Graph Theory": Date
Attention models in graphs: a survey
Lee J., Rossi R., Kim S., Ahmed N., Koh E.  ACM Transactions on Knowledge Discovery from Data 13(6): 1-25, 2019. Type: Article
Sep 20 2021
Exact transversal hypergraphs and application to Boolean -functions
Eiter T.  Journal of Symbolic Computation 17(3): 215-225, 1994. Type: Article, Reviews: (2 of 2)
Nov 26 2020
Graph theory and its applications (3rd ed.)
Gross J., Yellen J., Anderson M.,  Chapman&Hall/CRC, Boca Raton, FL, 2018. 591 pp. Type: Book (978-1-482249-48-4)
Oct 23 2019

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2021 ThinkLoud, Inc.
Terms of Use
| Privacy Policy