Re-embedding of projective-planar graphs

DOI10.1016/0095-8956(88)90037-8MaRDI QIDQ1086579zbMATH OpenOpenAlexFDO

Authors Seiya Negami

Publication date 1988

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0095-8956(88)90037-8

zbMATH Keywords

embedding of graphs in surfacesprojective planar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Review text

Let G be a graph embedded in a surface \(F^ 2\). An embedding \(f: G\to F^ 2\) is called a re-embedding of G in \(F^ 2\) if f cannot extend to a self-homeomorphism \(h: F^ 2\to F^ 2\) with \(h| _ G=f\). In this paper, re-embeddings of 3-connected nonplanar graphs embedded in the projective plane are classified into five types with respect to how bridges for the boundary cycle of a face are re-embedded. This classification theorem, called Re-embedding Theorem, is used to show that 5-connected projective-planar graphs with a certain condition are uniquely and faithfully embeddable in the projective plane.

Recommendations

• Unique and faithful embeddings of projective-planar graphs
• Re-embedding structures of 4-connected projective-planar graphs
• Unique embeddings of simple projective plane polyhedral maps
• Re-embedding structures of 5-connected projective-planar graphs
• Bounding the number of embeddings of 5-connected projective-planar graphs

Cites work

• Unique and faithful embeddings of projective-planar graphs
• Uniquely and faithfully embeddable projective-planar triangulations
• Uniqueness and faithfulness of embedding of toroidal graphs

Cited in

(24)

• Representations of graphs and networks (coding, layouts and embeddings)
• The 2 and 3 representative projective planar embeddings
• Re-embedding structures of 5-connected projective-planar graphs
• Closed 2-cell embeddings of 4 cross-cap embeddable graphs
• The closed 2-cell embeddings of 2-connected doubly toroidal graphs
• Planar graphs on the projective plane
• On minimum-genus embeddings
• Orientable embeddings and orientable cycle double covers of projective-planar graphs
• Panel structures of triangulations on the torus
• Face-width of embedded graphs
• Faithful embeddings of planar graphs on orientable closed surfaces
• Re-embeddings of Maximum 1-Planar Graphs
• Re-embedding structures of 4-connected projective-planar graphs
• scientific article; zbMATH DE number 5121865 (Why is no real title available?)
• Flexibility of projective-planar embeddings
• Unique and faithful embeddings of projective-planar graphs
• scientific article; zbMATH DE number 3952791 (Why is no real title available?)
• scientific article; zbMATH DE number 3995712 (Why is no real title available?)
• One-sided fattening of the graph in the real projective plane
• Faithful embeddings of planar graphs on nonorientable closed surfaces
• Re-1-embeddings of optimal 1-embedded graphs on the projective plane
• On delta-wye reducibility of toroidal graphs
• The variety of triangular embeddings of a graph in the projective plane
• Number of embeddings of circular and Möbius ladders on surfaces

This page was built for publication: Re-embedding of projective-planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1086579)