We show how to compute a maximum upward planar singlesource subgraph of a single-source embedded DAG Gφ. We first show that finding a maximum upward planar subgraph of a single-source embedded digraph is NP-complete. We then give a new characterization of upward planar single-source digraphs. We use this characterization to present an algorithm that computes a maximum upward planar single-source subgraph of a single-source embedded DAG. This algorithm takes O(n4) time in the worst case and O(n3) time on average.
['Aimal Rextin', 'Patrick Healy']
Maximum upward planar subgraph of a single-source embedded digraph