Triangulating a surface with a prescribed graph

DOI10.1006/jctb.1993.1016zbMath0794.05025OpenAlexW2074411730MaRDI QIDQ1325240

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) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Eulerian and Hamiltonian graphs (05C45)

Related Items

Unnamed Item ⋮ The genus of a random graph ⋮ Minimal quadrangulations of surfaces ⋮ Approximation Algorithms for Euler Genus and Related Problems ⋮ Counterexamples to the nonorientable genus conjecture for complete tripartite graphs ⋮ Face covers and the genus problem for apex graphs ⋮ Embeddings of graphs