Triangulating a surface with a prescribed graph

DOI10.1006/jctb.1993.1016zbMath0794.05025MaRDI 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

surface; embeddings; Hamiltonian cycles; NP-complete; perfect matching; Euler's formula; cubic bipartite graph; triangulation problem; graph genus problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C10: Planar graphs; geometric and topological aspects of graph theory

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C45: Eulerian and Hamiltonian graphs

Related Items

Embeddings of graphs, The genus of a random graph