Embeddings of graphs with no short noncontractible cycles

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

Carsten Thomassen

Publication date: 1990

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(90)90115-g

zbMATH Keywords

triangulationsminimum genus embedding2-cell embeddings of connected graphs into closed orientable 2-manifoldslarge edge widthLEWLEW-embedding

Mathematics Subject Classification ID

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

Related Items

The cycle's structure of embedded graphs in surfaces, Generating cycle spaces for graphs on surfaces with small genera, Unnamed Item, Bounded face-width forces \(K_7\)-minors in orientable surfaces, Graphs obtained from Moufang loops and regular maps, Short cycle structures for graphs on surfaces and an open problem of Mohar and Thomassen, A simpler proof of the excluded minor theorem for higher surfaces, Uniqueness and minimality of large face-width embeddings of graphs, A simple construction of high representativity triangulations, Planar graphs on the projective plane, Color-critical graphs on a fixed surface, Apex graphs with embeddings of face-width three, Orienting cycle elements in orientable rotation systems, Computing the shortest essential cycle, Upper embeddability of graphs, Approximation Algorithms for Euler Genus and Related Problems, Almost all rooted maps have large representativity, From Invariants to Canonization in Parallel, Algorithms for the edge-width of an embedded graph, Embeddability of arrangements of pseudocircles and graphs on surfaces, Densely embedded graphs, Catalan structures and dynamic programming in \(H\)-minor-free graphs, Topologically trivial closed walks in directed surface graphs, Face-width of Pfaffian braces and polyhex graphs on surfaces, Finding a shortest cycle in a subspace of the cycle space of a graph, Minimum cycle bases of graphs on surfaces, Short cycle structure of graphs on surfaces. I: The uniqueness theorems, Unnamed Item, Regular maps on surfaces with large planar width, On the uniqueness of kernels, Finding short cycles in embedded graph in polynomial time, Unnamed Item, 2- and 3-factors of graphs on surfaces, Finding shorter cycles in a weighted graph, Planar and grid graph reachability problems, Stronger ILPs for the Graph Genus Problem., A simple and elementary proof of Whitney's unique embedding theorem, Lower bounds for electrical reduction on surfaces, Generating locally-cyclic triangulations of surfaces, Generalized duality for graphs on surfaces and the signed Bollobás-Riordan polynomial, Fractional Coloring Methods with Applications to Degenerate Graphs and Graphs on Surfaces, Tilings of the Torus and the Klein Bottle and Vertex-Transitive Graphs on a Fixed Surface, Disjoint paths, planarizing cycles, and spanning walks, 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, Unnamed Item, Embeddings of graphs, Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable, Nonplanar graphs and well-covered cycles, Circular embedding of planar graphs in nonspherical surfaces, Projective plane embeddings of polyhedral pinched maps, The complexity of separating points in the plane

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