Existence of polyhedral embeddings of graphs

DOI10.1007/S004930100003MaRDI QIDQ5955209zbMATH OpenOpenAlexFDO

Authors Bojan Mohar

Publication date 13 February 2002

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.387.6171

zbMATH Keywords

face-widthHamilton cyclesNP-completenesspolyhedral embedding

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

\textit{C. Thomassen} [J. Comb. Theory, Ser. B 57, No. 2, 196--206 (1993; Zbl 0794.05025)] proved that the decision problem whether a given cubic bipartite graph contains two compatible Hamilton cycles is NP-complete. Here, the decision problem ``Does a given graph \(G\) have a polyhedral embedding is proven to be NP-complete by constructing, from a given 2-connected cubic bipartite graph \(G_0\) a 6-connected graph \(G_1\) which has a polyhedral embedding if and only if \(G_0\) has two compatible Hamilton cycles. Moreover, if \(G_1\) has a polyhedral embedding, it also has an orientable polyhedral embedding.

Recommendations

• Triangulating a surface with a prescribed graph
• scientific article; zbMATH DE number 3857154
• Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface
• Publication:4864467
• The genus problem for cubic graphs

Cited in

(10)

• Bounding the size of equimatchable graphs of fixed genus
• Triangulating a surface with a prescribed graph
• The genus problem for cubic graphs
• scientific article; zbMATH DE number 1078282 (Why is no real title available?)
• scientific article; zbMATH DE number 845923 (Why is no real title available?)
• On the genera of polyhedral embeddings of cubic graph
• Generating polyhedral quadrangulations of the projective plane
• A theorem on graph embedding with a relation to hyperbolic volume
• Scaffold for the polyhedral embedding of cubic graphs
• On embeddings of Grassmann graphs in polar Grassmann graphs

This page was built for publication: Existence of polyhedral embeddings of graphs

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