Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Recognizing weak embeddings of graphs
Akitaya H., Fulek R., Tóth C. ACM Transactions on Algorithms15 (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?
yes
no
Other reviews under "Graph Theory": Date
Graphs and algorithms
Gondran M., Minoux M. (ed), Vajda S., John Wiley & Sons, Inc., New York, NY, 1984. Type: Book (9789780471103745)
Jan 1 1985
On graph rewritings
Raoult J. Theoretical Computer Science 32(1-2): 1-24, 1984. Type: Article
Sep 1 1985
Non-partitionable point sets
Avis D. Information Processing Letters 19(3): 125-129, 1984. Type: Article
Jul 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy