Embedding graphs in the torus in linear time

DOI10.1007/3-540-59408-6_64MaRDI QIDQ5101428zbMATH OpenOpenAlexFDO

Authors 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

embedding extension problemlinear time algorithm

Mathematics Subject Classification ID

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

Recommendations

• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• scientific article; zbMATH DE number 1256757
• A large set of torus obstructions and how they were discovered
• scientific article; zbMATH DE number 2187701
• Edge Partition of Toroidal Graphs into Forests in Linear Time

Cites work

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

Cited in

(11)

• A large set of torus obstructions and how they were discovered
• 2-restricted extensions of partial embeddings of graphs
• Embedding graphs containing K₅-subdivisions on the torus
• scientific article; zbMATH DE number 2186718 (Why is no real title available?)
• Flexibility of embeddings of a Halin graph in the torus
• Edge Partition of Toroidal Graphs into Forests in Linear Time
• scientific article; zbMATH DE number 1256757 (Why is no real title available?)
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• scientific article; zbMATH DE number 2187701 (Why is no real title available?)
• scientific article; zbMATH DE number 2188433 (Why is no real title available?)
• Errors in graph embedding algorithms

This page was built for publication: Embedding graphs in the torus in linear time

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