Embedding graphs in the torus in linear time

DOI10.1007/3-540-59408-6_64zbMath1501.05016OpenAlexW1559483280MaRDI QIDQ5101428

Jože Marinček, Bojan Mohar, Martin Juvan

Publication date: 30 August 2022

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-59408-6_64

zbMATH Keywords

linear time algorithmembedding extension problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Errors in graph embedding algorithms, A large set of torus obstructions and how they were discovered, 2-restricted extensions of partial embeddings of graphs, Edge Partition of Toroidal Graphs into Forests in Linear Time

Cites Work

• Unnamed Item
• Unnamed Item
• Graph minors. XXII. Irrelevant vertices in linkage problems
• Graph minors. XXI. graphs with unique linkages
• An algorithm for imbedding cubic graphs in the torus
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• 2-restricted extensions of partial embeddings of graphs
• Graph minors. VIII: A Kuratowski theorem for general surfaces
• The graph genus problem is NP-complete
• Depth-First Search and Kuratowski Subgraphs
• Embedding Graphs in the Plane—Algorithmic Aspects
• Efficient Planarity Testing
• Dividing a Graph into Triconnected Components