Improving the running time of embedded upward planarity testing

Sarmad Abbasi; Patrick Healy; Aimal Rextin

doi:10.1016/j.ipl.2010.02.004

Improving the running time of embedded upward planarity testing

Sarmad Abbasi, Patrick Healy, Aimal Rextin

Department of Computer Science & Information Systems

Research output: Contribution to journal › Article › peer-review

Abstract

We consider the standard algorithm by Bertolazzi et al. to test the upward planarity of embedded digraphs. We show how to improve its running time from O (n + r²) to O (n + r^{frac(3, 2)}), where r is the number of sources and sinks in the digraph. We also discuss an application of this technique: improving the running time of getting a quasi-upward planar drawing for an embedded digraph with minimum number of bends.

Original language	English
Pages (from-to)	274-278
Number of pages	5
Journal	Information Processing Letters
Volume	110
Issue number	7
DOIs	https://doi.org/10.1016/j.ipl.2010.02.004
Publication status	Published - 1 Mar 2010

Keywords

Algorithms
Graph drawing
Upward planarity

Access to Document

10.1016/j.ipl.2010.02.004

Cite this

@article{1e78d9cfd04b4c37b4dc53819501feb4,

title = "Improving the running time of embedded upward planarity testing",

abstract = "We consider the standard algorithm by Bertolazzi et al. to test the upward planarity of embedded digraphs. We show how to improve its running time from O (n + r2) to O (n + rfrac(3, 2)), where r is the number of sources and sinks in the digraph. We also discuss an application of this technique: improving the running time of getting a quasi-upward planar drawing for an embedded digraph with minimum number of bends.",

keywords = "Algorithms, Graph drawing, Upward planarity",

author = "Sarmad Abbasi and Patrick Healy and Aimal Rextin",

year = "2010",

month = mar,

day = "1",

doi = "10.1016/j.ipl.2010.02.004",

language = "English",

volume = "110",

pages = "274--278",

journal = "Information Processing Letters",

issn = "0020-0190",

number = "7",

}

TY - JOUR

T1 - Improving the running time of embedded upward planarity testing

AU - Abbasi, Sarmad

AU - Healy, Patrick

AU - Rextin, Aimal

PY - 2010/3/1

Y1 - 2010/3/1

N2 - We consider the standard algorithm by Bertolazzi et al. to test the upward planarity of embedded digraphs. We show how to improve its running time from O (n + r2) to O (n + rfrac(3, 2)), where r is the number of sources and sinks in the digraph. We also discuss an application of this technique: improving the running time of getting a quasi-upward planar drawing for an embedded digraph with minimum number of bends.

AB - We consider the standard algorithm by Bertolazzi et al. to test the upward planarity of embedded digraphs. We show how to improve its running time from O (n + r2) to O (n + rfrac(3, 2)), where r is the number of sources and sinks in the digraph. We also discuss an application of this technique: improving the running time of getting a quasi-upward planar drawing for an embedded digraph with minimum number of bends.

KW - Algorithms

KW - Graph drawing

KW - Upward planarity

UR - http://www.scopus.com/inward/record.url?scp=77149126401&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2010.02.004

DO - 10.1016/j.ipl.2010.02.004

M3 - Article

AN - SCOPUS:77149126401

SN - 0020-0190

VL - 110

SP - 274

EP - 278

JO - Information Processing Letters

JF - Information Processing Letters

IS - 7

ER -

Improving the running time of embedded upward planarity testing

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this