Embeddings of graphs with no short noncontractible cycles

DOI10.1016/0095-8956(90)90115-GzbMath0704.05011MaRDI QIDQ916669

Carsten Thomassen

Publication date: 1990

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

zbMATH Keywords

triangulations; minimum genus embedding; 2-cell embeddings of connected graphs into closed orientable 2-manifolds; large edge width; LEW; LEW-embedding

Mathematics Subject Classification ID

05C38: Paths and cycles

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

Related Items

Almost all rooted maps have large representativity, Unnamed Item, Regular maps on surfaces with large planar width, Tilings of the Torus and the Klein Bottle and Vertex-Transitive Graphs on a Fixed Surface, Generating locally-cyclic triangulations of surfaces, Nonplanar graphs and well-covered cycles, Short cycle structures for graphs on surfaces and an open problem of Mohar and Thomassen, Densely embedded graphs, Upper embeddability of graphs, On the uniqueness of kernels, Embeddings of graphs, Circular embedding of planar graphs in nonspherical surfaces, Projective plane embeddings of polyhedral pinched maps, A simpler proof of the excluded minor theorem for higher surfaces, A simple construction of high representativity triangulations, Color-critical graphs on a fixed surface, Apex graphs with embeddings of face-width three, Orienting cycle elements in orientable rotation systems, Face size and the maximum genus of a graph. I: Simple graphs, Flexibility of polyhedral embeddings of graphs in surfaces, Long cycles in graphs on a fixed surface, Generating cycle spaces for graphs on surfaces with small genera, Uniqueness and minimality of large face-width embeddings of graphs, Planar graphs on the projective plane, Minimum cycle bases of graphs on surfaces, Unnamed Item, Disjoint paths, planarizing cycles, and spanning walks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Uniquely and faithfully embeddable projective-planar triangulations
• An infinite set of torus triangulations of connectivity 5 whose graphs are not uniquely embeddable in the torus
• Planarity and duality of finite and infinite graphs
• Uniqueness and faithfulness of embedding of toroidal graphs
• Construction and enumeration of regular maps on the torus
• The graph genus problem is NP-complete
• Automorphism properties of embedded graphs
• Efficient Planarity Testing
• Additivity of the genus of a graph
• How to Draw a Graph