TY - GEN
T1 - An improved upward planarity testing algorithm and related applications
AU - Abbasi, Sarmad
AU - Healy, Patrick
AU - Rextin, Aimal
PY - 2009
Y1 - 2009
N2 - We consider the standard algorithm to test the upward planarity of embedded digraphs by Bertolazzi et al. [3]. We show how to improve its running time from O(n + r 2) to O(n + r 3/2 ), where r is the number of sources and sinks in the digraph.We also discuss 2 applications of this technique: finding a certificate of correctness of an implementation of our upward planarity testing algorithm; and 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 to test the upward planarity of embedded digraphs by Bertolazzi et al. [3]. We show how to improve its running time from O(n + r 2) to O(n + r 3/2 ), where r is the number of sources and sinks in the digraph.We also discuss 2 applications of this technique: finding a certificate of correctness of an implementation of our upward planarity testing algorithm; and improving the running time of getting a quasi-upward planar drawing for an embedded digraph with minimum number of bends.
UR - http://www.scopus.com/inward/record.url?scp=67650434068&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-00202-1_29
DO - 10.1007/978-3-642-00202-1_29
M3 - Conference contribution
AN - SCOPUS:67650434068
SN - 3642002013
SN - 9783642002014
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 334
EP - 344
BT - WALCOM
T2 - 3rd International Workshop on Algorithms and Computation, WALCOM 2009
Y2 - 18 February 2009 through 20 February 2009
ER -