Triangulating a surface with a prescribed graph

DOI10.1006/JCTB.1993.1016MaRDI QIDQ1325240zbMATH OpenOpenAlexFDO

Authors Carsten Thomassen

Publication date 1 September 1994

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

Full work available at URL https://doi.org/10.1006/jctb.1993.1016

zbMATH Keywords

surfaceembeddingsHamiltonian cyclesNP-completeperfect matchingEuler's formulacubic bipartite graphtriangulation problemgraph genus problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• The genus problem for cubic graphs
• Existence of polyhedral embeddings of graphs
• scientific article; zbMATH DE number 867666
• Face covers and the genus problem for apex graphs

Cited in

(11)

• scientific article; zbMATH DE number 4066918 (Why is no real title available?)
• Embeddings of graphs
• The genus of a random graph
• Pairs of trees in tree--tree triangulations
• Subhamiltonian toroidal graphs
• Face covers and the genus problem for apex graphs
• Approximation algorithms for Euler genus and related problems
• Counterexamples to the nonorientable genus conjecture for complete tripartite graphs
• Existence of polyhedral embeddings of graphs
• Face-width of embedded graphs
• Minimal quadrangulations of surfaces

This page was built for publication: Triangulating a surface with a prescribed graph

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