Directed circuits on a torus

DOI10.1007/BF01205078MaRDI QIDQ1180428zbMATH OpenOpenAlexFDO

Authors Paul Seymour

Publication date 27 June 1992

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01205078

zbMATH Keywords

circuitsdigraph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38)

Review text

The author gives a polynomial algorithm for deciding if any two vertices of a digraph lie in a directed circuit. In addition, a polynomial algorithm is given for deciding the presence of a collection of disjoint directed circuits of prescribed homotopy in a digraph drawn on a torus.

Recommendations

• Disjoint cycles in directed graphs on the torus and the Klein bottle
• scientific article; zbMATH DE number 166022
• Packing directed circuits
• A polynomial algorithm for hamiltonian-connectedness in semicomplete digraphs
• On digraphs with no two disjoint directed cycles

Cites work

• Graph minors. VI. Disjoint paths across a disc
• The directed subgraph homeomorphism problem

Cited in

(7)

• Circuits in graphs embedded on the torus
• Disjoint circuits on a Klein bottle and a theorem on posets
• Disjoint cycles in directed graphs on the torus and the Klein bottle
• Determination of a circuit in a directed graph
• scientific article; zbMATH DE number 166022 (Why is no real title available?)
• scientific article; zbMATH DE number 475589 (Why is no real title available?)
• A Polynomial Algorithm for Homomorphisms to Oriented Cycles

This page was built for publication: Directed circuits on a torus

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