Computing maximum upward planar subgraphs of single-source embedded digraphs

Aimal Rextin; Patrick Healy

doi:10.1007/s10878-010-9373-z

Computing maximum upward planar subgraphs of single-source embedded digraphs

Aimal Rextin, Patrick Healy

National University of Sciences and Technology Pakistan

Research output: Contribution to journal › Article › peer-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 ⁴) time in the worst case and O(n ³) time on average.

Original language	English
Pages (from-to)	368-392
Number of pages	25
Journal	Journal of Combinatorial Optimization
Volume	25
Issue number	3
DOIs	https://doi.org/10.1007/s10878-010-9373-z
Publication status	Published - Apr 2013

Keywords

Graph drawing
Single-source digraphs
Upward planarity

Access to Document

10.1007/s10878-010-9373-z

Cite this

@article{96b0ae2ce0a0468f95fb168b403c39c1,

title = "Computing maximum upward planar subgraphs of single-source embedded digraphs",

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.",

keywords = "Graph drawing, Single-source digraphs, Upward planarity",

author = "Aimal Rextin and Patrick Healy",

year = "2013",

month = apr,

doi = "10.1007/s10878-010-9373-z",

language = "English",

volume = "25",

pages = "368--392",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

number = "3",

}

TY - JOUR

T1 - Computing maximum upward planar subgraphs of single-source embedded digraphs

AU - Rextin, Aimal

AU - Healy, Patrick

PY - 2013/4

Y1 - 2013/4

N2 - 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.

AB - 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.

KW - Graph drawing

KW - Single-source digraphs

KW - Upward planarity

UR - https://www.scopus.com/pages/publications/84879607151

U2 - 10.1007/s10878-010-9373-z

DO - 10.1007/s10878-010-9373-z

M3 - Article

AN - SCOPUS:84879607151

SN - 1382-6905

VL - 25

SP - 368

EP - 392

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 3

ER -

Computing maximum upward planar subgraphs of single-source embedded digraphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this