Upward planarity testing |
| |
Authors: | Ashim Garg Roberto Tamassia |
| |
Institution: | (1) Department of Computer Science, Brown University, 02912-1910 Providence, RI, U.S.A. |
| |
Abstract: | Acyclic digraphs, such as the covering digraphs of ordered sets, are usually drawn upward, i.e., with the edges monotonically increasing in the vertical direction. A digraph is upward planar if it admits an upward planar drawing. In this survey paper, we overview the literature on the problem of upward planarity testing. We present several characterizations of upward planarity and describe upward planarity testing algorithms for special classes of digraphs, such as embedded digraphs and single-source digraphs. We also sketch the proof of NP-completeness of upward planarity testing.Research supported in part by the National Science Foundation under grant CCR-9423847. |
| |
Keywords: | 05C10 06A99 68Q20 68R10 68U05 |
本文献已被 SpringerLink 等数据库收录! |
|