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

cubic bipartite graphembeddingsEuler's formulagraph genus problemHamiltonian cyclesNP-completeperfect matchingsurfacetriangulation problem

Mathematics Subject Classification ID

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) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

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

(14)

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

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)