Embeddings of graphs with no short noncontractible cycles

DOI10.1016/0095-8956(90)90115-GzbMATH Open0704.05011OpenAlexW2025861110MaRDI QIDQ916669FDOQ916669

Authors: 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

Recommendations

• Structures of facial cycles and \(C\)-bridges of embedded graphs with locally LEW-embedding properties
• scientific article; zbMATH DE number 2163939
• Algorithms for the edge-width of an embedded graph
• Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
• On Short Noncontractible Cycles in Embedded Graphs

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (61)

• Disjoint paths, planarizing cycles, and spanning walks
• Graphs obtained from Moufang loops and regular maps
• Planar and grid graph reachability problems
• The complexity of separating points in the plane
• Topologically trivial closed walks in directed surface graphs
• The cycle's structure of embedded graphs in surfaces
• Algorithms for the edge-width of an embedded graph
• Embeddings of graphs
• Short cycle structures for graphs on surfaces and an open problem of Mohar and Thomassen
• Circular embedding of planar graphs in nonspherical surfaces
• Generating locally-cyclic triangulations of surfaces
• On a Lower Bound for Short Noncontractible Cycles in Embedded Graphs
• Title not available (Why is that?)
• Minimum cycle bases of graphs on surfaces
• Weighted graphs permitting no LEW-embeddings
• Color-critical graphs on a fixed surface
• Orienting cycle elements in orientable rotation systems
• 2- and 3-factors of graphs on surfaces
• Lower bounds for electrical reduction on surfaces
• Approximation algorithms for Euler genus and related problems
• Long cycles in graphs on a fixed surface
• Computing the shortest essential cycle
• Regular maps on surfaces with large planar width
• Generating cycle spaces for graphs on surfaces with small genera
• Bounded face-width forces \(K_7\)-minors in orientable surfaces
• Catalan structures and dynamic programming in \(H\)-minor-free graphs
• Almost all rooted maps have large representativity
• Generalized duality for graphs on surfaces and the signed Bollobás-Riordan polynomial
• Densely embedded graphs
• A simple and elementary proof of Whitney's unique embedding theorem
• Face-width of embedded graphs
• Title not available (Why is that?)
• On the uniqueness of kernels
• 2-IRREDUCIBILITY OF SPATIAL GRAPHS
• Structures of facial cycles and \(C\)-bridges of embedded graphs with locally LEW-embedding properties
• Face-width of Pfaffian braces and polyhex graphs on surfaces
• Algorithms – ESA 2005
• Projective plane embeddings of polyhedral pinched maps
• A simpler proof of the excluded minor theorem for higher surfaces
• From Invariants to Canonization in Parallel
• Global minimum cuts in surface embedded graphs
• Face size and the maximum genus of a graph. I: Simple graphs
• A simple construction of high representativity triangulations
• Embeddability of arrangements of pseudocircles and graphs on surfaces
• Nonplanar graphs and well-covered cycles
• Finding a shortest cycle in a subspace of the cycle space of a graph
• Apex graphs with embeddings of face-width three
• Short cycle structure of graphs on surfaces. I: The uniqueness theorems
• Tilings of the Torus and the Klein Bottle and Vertex-Transitive Graphs on a Fixed Surface
• Upper embeddability of graphs
• Flexibility of polyhedral embeddings of graphs in surfaces
• Uniqueness and minimality of large face-width embeddings of graphs
• Planar graphs on the projective plane
• Finding short cycles in embedded graph in polynomial time
• Towards geodesic ridge curve for region-wise linear representation of geodesic distance field
• Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
• Fractional coloring methods with applications to degenerate graphs and graphs on surfaces
• Finding shorter cycles in a weighted graph
• Stronger ILPs for the Graph Genus Problem.
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: Embeddings of graphs with no short noncontractible cycles

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