×

Disjoint circuits of prescribed homotopies in a graph on a compact surface. (English) Zbl 0723.05050

Necessary and sufficient conditions are given for the existence of pairwise vertex-disjoint simple closed curves \(\tilde C_ 1,...,\tilde C_ k\), homotopic to given closed curves \(C_ 1,...,C_ k\) (respectively), in a graph imbedded in a compact surface. This proves a conjecture of L. Lovász and P. D. Seymour.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ahlfors, L. V.; Sario, L., (Riemann Surfaces (1960), Princeton Univ. Press: Princeton Univ. Press Princeton, NJ) · Zbl 0196.33801
[2] Baer, R., Kurventypen auf Flächen, J. Reine Angew. Math., 156, 231-246 (1927) · JFM 53.0547.01
[3] Cole, R.; Siegel, A., River routing every which way, but loose, (Proc. 25th Ann. Symp. Foundations of Computer Sci. (1984)), 65-73
[4] Dehn, M.; Heegaard, P., Analysis situs, (Encyclopädie der mathematischen Wissenschaften, III. Band (1907-1910), Teubner: Teubner Leipzig), 153-220, I. Teil, I. Hälfte · JFM 38.0510.14
[5] Fenn, R. A., (Techniques of Geometric Topology (1983), Cambridge Univ. Press: Cambridge Univ. Press Cambridge, UK)
[6] Goldman, M. E., An algebraic classification of noncompact 2-manifolds, Trans. Amer. Math. Soc., 156, 241-258 (1971) · Zbl 0232.57007
[7] von Kerékjártó, B., (Vorlesungen über Topologie I: Flächentopologie (1923), Springer-Verlag: Springer-Verlag Berlin) · JFM 49.0396.07
[8] Leiserson, C. E.; Maley, F. M., Algorithms for routing and testing routability of planar VLSI-layouts, (Proc. 17th Ann. ACM Symp. Theory of Computing (1985)), 69-78
[9] Massey, W. S., (Algebraic Topology: An Introduction (1967), Springer-Verlag: Springer-Verlag New York) · Zbl 0153.24901
[10] Moise, E. E., (Geometric Topology in Dimensions 2 and 3 (1977), Springer-Verlag: Springer-Verlag New York) · Zbl 0349.57001
[11] Pinter, R. Y., River routing: methodology and analysis, (Third CalTech Conf. on Very Large Scale Integration (1983), Springer-Verlag: Springer-Verlag Berlin), 141-163
[12] Poincaré, H., 5e complément à l’Analysis Situs, Rend. Circ. Mat. Palermo, 18, 45-110 (1904) · JFM 35.0504.13
[13] Radó, T., Über den Begriff der Riemannschen Fläche, Acta Litt. Sci. Szeged, 2, 101-121 (1925) · JFM 51.0273.01
[14] Richards, I., On the classification of noncompact surfaces, Trans. Amer. Math. Soc., 106, 259-269 (1963) · Zbl 0156.22203
[15] Robertson, N.; Seymour, P. D., Graph minors. VI. Disjoint paths across a disc, J. Combin. Theory Ser. B, 41, 115-138 (1986) · Zbl 0598.05042
[16] Robertson, N.; Seymour, P. D., Graph minors. VII. Disjoint paths on a surface, J. Combin. Theory Ser. B, 45, 212-254 (1988) · Zbl 0658.05044
[17] Seifert, H.; Threlfall, W., (Lehrbuch der Topologie (1934), Teubner: Teubner Leipzig). (A Textbook of Topology (1980), Teubner: Teubner New York), English translation
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.