Computing maximum upward planar subgraphs of single-source embedded digraphs

Aimal Rextin, Patrick Healy

Research output: Contribution to journalArticlepeer-review

Abstract

We show how to compute a maximum upward planar single-source 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(n 4) time in the worst case and O(n 3) time on average.

Original languageEnglish
Pages (from-to)368-392
Number of pages25
JournalJournal of Combinatorial Optimization
Volume25
Issue number3
DOIs
Publication statusPublished - Apr 2013

Keywords

  • Graph drawing
  • Single-source digraphs
  • Upward planarity

Fingerprint

Dive into the research topics of 'Computing maximum upward planar subgraphs of single-source embedded digraphs'. Together they form a unique fingerprint.

Cite this