Checkerboard embeddings of *-graphs into nonorientable surfaces

DOI10.1142/S0218216514600049MaRDI QIDQ2930982zbMATH OpenOpenAlexFDO

Authors Tyler Friesen, V. O. Manturov

Publication date 21 November 2014

Published in Journal of Knot Theory and Its Ramifications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.6342

zbMATH Keywords

surfaceembeddinggenus\(\ast\)-graph

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex degrees (05C07) Relations of low-dimensional topology with graph theory (57M15)

Abstract: This paper considers *-graphs in which all vertices have degree 4 or 6, and studies the question of calculating the genus of nonorientable surfaces into which such graphs may be embedded. In a previous paper by the authors, the problem of calculating whether a given *-graph in which all vertices have degree 4 or 6 admits a Z2-homologically trivial embedding into a given orientable surface was shown to be equivalent to a problem on matrices. Here we extend those results to nonorientable surfaces. The embeddability condition that we obtain yields quadratic-time algorithms to determine whether a *-graph with all vertices of degree 4 or 6 admits a Z2-homologically trivial embedding into the projective plane or into the Klein bottle.

Recommendations

• Embeddings of \(\ast\)-graphs into 2-surfaces
• Embedding digraphs on orientable surfaces
• scientific article; zbMATH DE number 772738
• scientific article; zbMATH DE number 1457375
• scientific article; zbMATH DE number 5584098
• Faithful embeddings of planar graphs on nonorientable closed surfaces
• A characterization of embeddability of graphs on surfaces
• scientific article; zbMATH DE number 867667
• Embeddability of arrangements of pseudocircles and graphs on surfaces
• Surface Embedding of Non-Bipartite $k$-Extendable Graphs

Cites work

• An obstruction to embedding graphs in surfaces
• Cycle decomposition by disjoint transpositions
• VASSILIEV KNOT INVARIANTS COMING FROM LIE ALGEBRAS AND 4-INVARIANTS

Cited in

(3)

• Embeddings of \(\ast\)-graphs into 2-surfaces
• Framed 4-valent graph minor theory II: Special minors and new examples
• Graphs 2-cell embedded in non-orientable surfaces and their coding sequences

This page was built for publication: Checkerboard embeddings of *-graphs into nonorientable surfaces

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