Finding All Useless Arcs in Directed Planar Graphs
Published in arXiv, 2017
Recommended citation: Fakcharoenphol, Jittat, Bundit Laekhanukit, and Pattara Sukprasert. "Finding all useless arcs in directed planar graphs." arXiv preprint arXiv:1702.04786 (2017). https://arxiv.org/abs/1702.04786
Given a directed planar graph, a source vertex, and a sink vertex. We propose an algorithm to remove all arcs not participating in any simple path from source to sink in linear-time.