Back to Search
Start Over
Optimal upward planarity testing of single-source digraphs
- Source :
- SIAM journal on computing, 27 (1998): 132–169., info:cnr-pdr/source/autori:Bertolazzi P., Di Battista G., Mannino C., Tamassia R./titolo:Optimal upward planarity testing of single-source digraphs/doi:/rivista:SIAM journal on computing (Print)/anno:1998/pagina_da:132/pagina_a:169/intervallo_pagine:132–169/volume:27, Scopus-Elsevier
- Publication Year :
- 1998
- Publisher :
- Society for Industrial and Applied Mathematics., [Philadelphia], Stati Uniti d'America, 1998.
-
Abstract
- A digraph is upward planar if it has a planar drawing such that all the edges are monotone with respect 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 previously known best result is an O(n2)-time algorithm by Hutton and Lubiw [Proc. 2nd ACM--SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 1991, pp. 203--211]. No efficient parallel algorithms for upward planarity testing were previously known.
- Subjects :
- Discrete mathematics
SPQR tree
General Computer Science
General Mathematics
Parallel algorithm
planar graph
upward drawing
Graph theory
Digraph
Computer Science::Computational Geometry
Planarity testing
Upward planar drawing
Planar graph
Combinatorics
graph drawing
symbols.namesake
Graph drawing
parallel algorithm
TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY
symbols
triconnected components
MathematicsofComputing_DISCRETEMATHEMATICS
Mathematics
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- SIAM journal on computing, 27 (1998): 132–169., info:cnr-pdr/source/autori:Bertolazzi P., Di Battista G., Mannino C., Tamassia R./titolo:Optimal upward planarity testing of single-source digraphs/doi:/rivista:SIAM journal on computing (Print)/anno:1998/pagina_da:132/pagina_a:169/intervallo_pagine:132–169/volume:27, Scopus-Elsevier
- Accession number :
- edsair.doi.dedup.....30c577bfce981e7203b5eed10f8469c1