Lifting Maps Between Graphs to Embeddings

Alexey Gorelov ()
Additional contact information
Alexey Gorelov: Institut Fourier, Université Grenoble Alpes, CNRS

Chapter Chapter 16 in Essays on Topology, 2025, pp 327-364 from Springer

Abstract: Abstract In this chapter, we study conditions for the existence of an embedding f ˜ : P → Q × ℝ $$\widetilde {f} \colon P \to Q \times \mathbb {R}$$ such that f = pr Q ∘ f ˜ $$f = \operatorname {\mathrm {pr}}_Q \circ \widetilde {f}$$ , where f : P → Q $$f \colon P \to Q$$ is a piecewise linear map between polyhedra. Our focus is on non-degenerate maps between graphs, where non-degeneracy means that the preimages of points are finite sets. We introduce combinatorial techniques and establish necessary and sufficient conditions for the general case. Using these results, we demonstrate that the problem of the existence of a lifting reduces to testing the satisfiability of a 3-CNF formula. Additionally, we construct a counterexample to a result by V. Poénaru on lifting of smooth immersions to embeddings. Furthermore, by establishing connections between the stated problem and the approximability by embeddings, we deduce that, in the case of generic maps from a tree to a segment, a weaker condition becomes sufficient for the existence of a lifting.

Keywords: Graph; Polyhedron; Simplicial complex; Embedding; Computational topology; Primary 05C10, 57M15, 57Q35; Secondary 57N35, 05E45 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-031-81414-3_16

Ordering information: This item can be ordered from
http://www.springer.com/9783031814143

DOI: 10.1007/978-3-031-81414-3_16

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().