Improving the running time of embedded upward planarity testing |
| |
Authors: | Sarmad Abbasi |
| |
Affiliation: | a 117-BB, Phase IV, DHA, Lahore, Pakistan b Computer Science Department, University of Limerick, Ireland |
| |
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 , 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 |
本文献已被 ScienceDirect 等数据库收录! |
|