Combinatorial Local Planarity and the Width of Graph Embeddings

Mohar, Bojan

Canadian journal of mathematics, Tome 44 (1992) no. 6, pp. 1272-1288

Résumé

Let G be a graph embedded in a closed surface. The embedding is “locally planar” if for each face, a “large” neighbourhood of this face is simply connected. This notion is formalized, following [RV], by introducing the width ρ(ψ) of the embedding ψ. It is shown that embeddings with ρ(ψ) ≥ 3 behave very much like the embeddings of planar graphs in the 2-sphere. Another notion, “combinatorial local planarity”, is introduced. The criterion is independent of embeddings of the graph, but it guarantees that a given cycle in a graph G must be contractible in any minimal genus embedding of G (either orientable, or non-orientable). It generalizes the width introduced before. As application, short proofs of some important recently discovered results about embeddings of graphs are given and generalized or improved. Uniqueness and switching equivalence of graphs embedded in a fixed surface are also considered.

Détail

DOI : 10.4153/CJM-1992-076-8

Mots-clés : 05C10, 57M15

Bibliographie

[B] Barnette, D.W., Unique embeddings of simple projective plane polyhedral maps, Isr. J. Math. 67(1989), 251–256. Google Scholar

[BHKY] Battle, J., Harary, F., Kodama, Y. and Youngs, J.W.T.., Additivity of the genus of a graph, Bull. Amer. Math. Soc. 68(1962), 565–568. Google Scholar

[FHRR] Fiedler, J.R., Huneke, J.P., Richter, R.B. and Robertson, N., Computing the orientable genus of projective graphs, preprint, 1989. Google Scholar

[HR] Hoffman, P. and Richter, B., Embedding graphs in surfaces, J. Combin. Theory (B) 36(1984), 65–84. Google Scholar

[L] Lavrenchenko, S.A., On the number of triangular embeddings of a labelled graph in the projective plane, (in Russian), Ukrain. Geom. Sb. 32(1989), 71–84. Google Scholar

[M] Mohar, B., The orientable genus of graphs with bounded non-orientable genus, in preparation. Google Scholar

[MRV] Mohar, B., Robertson, N. and Vitray, R.P., Planar graphs on non-planar surfaces I. The projective plane, submitted. Google Scholar

[Nl] Negami, S., Unique and faithful embeddings of projective planar graphs, J. Graph Theory 9(1985), 235- 243. Google Scholar

[N2] Negami, S., Re-embedding of projective-planar graphs, J. Combin. Theory (B) 44(1988), 276–299. Google Scholar

[R] Richter, R.B., On the non-orientable genus of a 2-connected graph, J. Combin. Theory (B) 43(1987), 48–59. Google Scholar

[RS] Robertson, N. and Seymour, P.D., Graph minors VII. Disjoint paths on a surface, J. Combin. Theory (B) 45(1988), 212–254. Google Scholar

[RV] Robertson, N. and Vitray, R.P., Representative of surface embeddings. In: Paths, Flows, and VLSI-Layout, (eds. Korte, B., Lov, L.âsz, Promel, H.J., and Schrijver, A.), Springer-Verlag, Berlin, 1990, 293–328. Google Scholar

[SB] Stahl, S. and Beineke, L., Blocks and the non-orientable genus of a graph, J. Graph Theory 1(1977), 75–78. Google Scholar

[Tl] Thomassen, C.,Embeddings of graphs with no short noncontractible cycles, J. Combin. Theory (B) 48(1990), 155–177. Google Scholar

[T2] Thomassen, C., The graph genus problem is NP-complete, J. Algorithms 10(1989), 568–576. Google Scholar

[T3] Thomassen, C., Triangulating a surface with a prescribed graph, to appear. Google Scholar

[T\il] Tutte, W.T., Graph Theory, Cambridge Univ. Press, Cambridge, 1984. Google Scholar

[T\i2] Tutte, W.T., How to draw a graph, Proc. London Math. Soc. 13(1963), 743–768. Google Scholar

[WB] White, A.T. and Beineke, L.W., Topological graph theory. In: Selected Topics in Graph Theory, (eds. Beineke, L.W. and Wilson, R.J.), Academic Press, 1978, 15–50. Google Scholar

[W] Whitney, H., 2-isomorphic graphs, Amer. Math. J. 55(1933), 245–254. Google Scholar