Rooted routing in the plane

DOI10.1016/0166-218X(94)00104-LzbMath0816.05050MaRDI QIDQ1346696

Bruce A. Reed

Publication date: 10 April 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

partition; trees; realization; plane; linear-time algorithm; higher-genus surfaces; rooted routing

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

68R10: Graph theory (including graph drawing) in computer science

05C38: Paths and cycles

05C10: Planar graphs; geometric and topological aspects of graph theory

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

The disjoint paths problem in quadratic time, A linear time algorithm for the induced disjoint paths problem in planar graphs, Algorithms for finding an induced cycle in planar graphs, Linear time algorithms for two disjoint paths problems on directed acyclic graphs, The Induced Disjoint Paths Problem, An Improved Algorithm for Finding Cycles Through Elements

Cites Work

• Graph minors. VI. Disjoint paths across a disc
• Graph minors. VII: Disjoint paths on a surface
• Disjoint paths in graphs
• Graph minors. XIII: The disjoint paths problem
• Graph minors. II. Algorithmic aspects of tree-width
• A Polynomial Solution to the Undirected Two Paths Problem
• On the Computational Complexity of Combinatorial Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item