Publications of Paola Bertolazzi

This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  1994, with author Bertolazzi P., in the category IASI Research Reports (or show them all):


IASI Research Report n. 396  


Paola Bertolazzi, Di Battista G., Mannino C., Tamassia R.

Optimal upward planarity testing of single-source digraphs

ABSTRACT
A digraphs is upward planar if it has a planar drawing such that all the edges are monotone with repsect to the vertical direction. Testing upward planarity and constructing upward planar drawings is important for displaying hierarchical network structures, which frequently arise in software engineering, project management, and visual languages. In this paper we investigate upward planarity testing of single-source digraphs: we provide a new combinatorial characterization of upward planarity, and give an optimal algorithm for upward planarity testing. Our algorithm tests whether a single-source digraph with n vertices is upward planar in O(n) sequential time, and in O(log n) time on a CRCW PRAM with n log log n/ log n processors, using O(n) space. The algorithm also constructs an upward planar drawing if the test is successful. The previous best result is an O(n^2)-time algorithm by Hutton and Lubiw. No efficient parallel algorithms for upward planarity testing were previously known.
back
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -