Errors in graph embedding algorithms

DOI10.1016/j.jcss.2010.06.002zbMath1213.05252OpenAlexW2077000739MaRDI QIDQ632808

William L. Kocay, Wendy J. Myrvold

Publication date: 28 March 2011

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2010.06.002

zbMATH Keywords

algorithmtorusgraph embeddinggraph genus

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Algorithms for the workflow satisfiability problem engineered for counting constraints ⋮ A large set of torus obstructions and how they were discovered ⋮ Practical graph isomorphism. II. ⋮ Stronger ILPs for the Graph Genus Problem. ⋮ New methods for finding minimum genus embeddings of graphs on orientable and non-orientable surfaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An algorithm for imbedding cubic graphs in the torus
• A new planarity test
• Efficient Planarity Testing
• Note on Hopcroft and Tarjan's Planarity Algorithm
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• Projective Planarity in Linear Time
• Graphs, Algorithms, and Optimization
• Fast generation of cubic graphs
• Embedding graphs in the torus in linear time
• An efficient algorithm for determining whether a cubic graph is toroidal
• Graph Drawing