×

Planar graphs on the projective plane. (English) Zbl 0849.05023

It is shown that embeddings of planar graphs in the projective plane necessarily have very specific structure, which leads to an indirect characterization of projective-planar graphs whose duals are planar. Also Whitney’s planar 2-switching theorem is generalized: Any two embeddings of a planar graph in the projective plane can be obtained from each other by means of simple local reembeddings (similar to Whitney’s switchings).

MSC:

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

References:

[1] Archdeacon, D., Densely embedded graphs, J. Combin. Theory Ser. B, 54, 13-36 (1992) · Zbl 0694.05024
[2] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), MacMillan: MacMillan New York · Zbl 1134.05001
[3] Negami, S., Re-embedding of projective-planar graphs, J. Combin. Theory Ser. B, 44, 276-299 (1988) · Zbl 0609.05033
[4] R.B. Richter, P.D. Seymour and J. Širáň, Circular embeddings of planar graphs in non-spherical surfaces, Discrete Math., in press.; R.B. Richter, P.D. Seymour and J. Širáň, Circular embeddings of planar graphs in non-spherical surfaces, Discrete Math., in press.
[5] 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
[6] Robertson, N.; Vitray, R. P., Representativity of surface embeddings, (Korte, B.; Lovász, L.; Prömel, H. J.; Schrijver, A., Paths, Flows and VLSI-Layout (1990), Springer: Springer Berlin), 293-328 · Zbl 0735.05032
[7] Shih, C.-H., On graphic subspaces of graphic spaces, (Ph.D. Thesis (1982), The Ohio State University: The Ohio State University Columbus, OH)
[8] Thomassen, C., Embeddings of graphs with no short non-contractible cycles, J. Combin. Theory. Ser. B, 48, 155-177 (1990) · Zbl 0704.05011
[9] Tutte, W. T., Connectivity in Graphs (1966), Univ. of Toronto Press: Univ. of Toronto Press Toronto · Zbl 0146.45603
[10] Tutte, W. T., Matroids and graphs, Trans. Amer. Math. Soc., 88, 144-174 (1958) · Zbl 0081.17301
[11] Vitray, R. P., Representativity and flexibility of drawings of graphs on the projective plane, (Ph.D. Thesis (1987), The Ohio State University: The Ohio State University Columbus, OH) · Zbl 0792.05048
[12] Whitney, H., 2-isomorphic graphs, Amer. J. Math., 55, 245-254 (1933) · JFM 59.1235.01
[13] B. Mohar and N. Robertson, Planar graphs on nonplanar surfaces, submitted.; B. Mohar and N. Robertson, Planar graphs on nonplanar surfaces, submitted. · Zbl 0856.05027
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.