The genus problem for cubic graphs
The NP-completeness of Ringel's problem of characterizing those graphs which triangulate some surface [Lect. Notes Math. 642, 455-475 (1978)] was established by the author [J. Comb. Theory, Ser. B 57, No. 2, 196-206 (1993; Zbl 0794.05025)]. In the present paper he considers the dual version, showing that the following problem is NP-complete. Given a cubic graph \(G\) and a natural number \(k\), is the genus of \(G\) at most \(k\)? The author observes that his proof extends to the nonorientable case and to \(r\)-regular graphs, for at least \(r=4\) and 5.
- Triangulating a surface with a prescribed graph
- Minimal quadrangulations of surfaces
- Settling the genus of the n-prism
- The genus of the balanced hypercube
- Embeddings of circular graphs
- scientific article; zbMATH DE number 3931037 (Why is no real title available?)
- The decycling number and maximum genus of cubic graphs
- Calculating genus polynomials via string operations and matrices
- The degenerate crossing number and higher-genus embeddings
- Enumerating graph embeddings and partial-duals by genus and Euler genus
- scientific article; zbMATH DE number 6297701 (Why is no real title available?)
- Existence of polyhedral embeddings of graphs
- Efficient polynomial-time approximation scheme for the genus of dense graphs
- Genus of the Cartesian product of triangles
This page was built for publication: The genus problem for cubic graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1354116)
