Checkerboard embeddings of *-graphs into nonorientable surfaces

DOI10.1142/S0218216514600049zbMATH Open1305.05051arXiv1312.6342OpenAlexW2096758564MaRDI QIDQ2930982FDOQ2930982

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)

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.

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

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

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)

Cites Work

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

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)