Edge Partition of Toroidal Graphs into Forests in Linear Time

DOI10.1016/J.ENDM.2005.06.065MaRDI QIDQ3439375zbMATH OpenOpenAlexFDO

Authors Nicolas Bonichon, Cyril Gavoille, Arnaud Labourel

Publication date 29 May 2007

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2005.06.065

zbMATH Keywords

graph algorithmgraph on surfacesgraph partitionSchnyder treesspanning tree

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• scientific article; zbMATH DE number 4108779
• Triangle-partitioning edges of planar graphs, toroidal graphs and \(k\)-planar graphs
• Decomposing toroidal graphs into circuits and edges
• Embedding graphs in the torus in linear time
• scientific article; zbMATH DE number 3946182

Cites work

• A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
• Bounds of the number of disjoint spanning trees
• Embedding graphs in the torus in linear time
• Five-coloring maps on surfaces
• scientific article; zbMATH DE number 432759 (Why is no real title available?)
• On the independence ratio of a graph

Cited in

(9)

• The structure of \(K_{3,3}\)-subdivision-free toroidal graphs
• Decomposing toroidal graphs into circuits and edges
• scientific article; zbMATH DE number 4108779 (Why is no real title available?)
• scientific article; zbMATH DE number 2075844 (Why is no real title available?)
• scientific article; zbMATH DE number 7366688 (Why is no real title available?)
• Embedding graphs in the torus in linear time
• Schnyder woods for higher genus triangulated surfaces (abstract)
• Computation of toroidal Schnyder woods made simple and fast: from theory to practice
• Schnyder woods for higher genus triangulated surfaces, with applications to encoding

This page was built for publication: Edge Partition of Toroidal Graphs into Forests in Linear Time

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