Relative embeddings of graphs on closed surfaces. (English) Zbl 0646.05024
If G is a connected graph and W is a set of closed walks in G, then a 2- cell embedding \(i: G\to S\) of G into a closed 2-manifold S is said to be a relative embedding of G with respect to W if each walk of W appears as a boundary of some 2-cell of i. In “Relative embeddings of graphs” [Graph theory, Proc. 6th Yugosl. Semin., Dubrovnik/Yugosl. 1985, 211-217 (1986; Zbl 0614.05021)] the authors announced existence and interpolation theorems, for both orientable and nonorientable surfaces, the relative embeddings of G with respect to W. in “Oriented relative embeddings of graphs” [Applications Mathematicae XIX, 3-4, 589-597 (1987)] they provided proofs for the orientable case; in the present paper, they provide proofs for the nonorientable case, and also investigate the relationship between realizability on orientable and nonorientable surfaces.
Reviewer: A.T.White
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 57M15 | Relations of low-dimensional topology with graph theory |
Citations:
Zbl 0614.05021References:
| [1] | Duke, Canad. J. Math. 18 pp 817– (1966) · Zbl 0141.21302 · doi:10.4153/CJM-1966-081-6 |
| [2] | and , Embedding a graph in a plane with certain constraints, IEEE Trans. Circuit Theory CT-17 (1970) 250–252 |
| [3] | Marx, Congressus Numerantium 33 pp 205– (1981) |
| [4] | Oubina, Discrete Math. 51 pp 243– (1984) |
| [5] | Map Color Theorem (Springer-Verlag, New York, 1974) · Zbl 0287.05102 · doi:10.1007/978-3-642-65759-7 |
| [6] | Stahl, J. Graph Theory 2 pp 41– (1978) |
| [7] | Graphs, Groups and Surfaces (North-Holland, Amsterdam, New York, Oxford, 1984) |
| [8] | and , Oriented relative embeddings of graphs, Applicationes Mathematicae XIX, 3–4. (1987) 589–597 · Zbl 0736.05035 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
