Embeddings of graphs with no short noncontractible cycles
From MaRDI portal
Publication:916669
DOI10.1016/0095-8956(90)90115-GzbMath0704.05011OpenAlexW2025861110MaRDI QIDQ916669
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
triangulationsminimum genus embedding2-cell embeddings of connected graphs into closed orientable 2-manifoldslarge edge widthLEWLEW-embedding
Related Items (53)
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
This page was built for publication: Embeddings of graphs with no short noncontractible cycles
