Upward planar drawings with two slopes
From MaRDI portal
Publication:5084713
Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)
Abstract: In an upward planar 2-slope drawing of a digraph, edges are drawn as straight-line segments in the upward direction without crossings using only two different slopes. We investigate whether a given upward planar digraph admits such a drawing and, if so, how to construct it. For the fixed embedding scenario, we give a simple characterisation and a linear-time construction by adopting algorithms from orthogonal drawings. For the variable embedding scenario, we describe a linear-time algorithm for single-source digraphs, a quartic-time algorithm for series-parallel digraphs, and a fixed-parameter tractable algorithm for general digraphs. For the latter two classes, we make use of SPQR-trees and the notion of upward spirality. As an application of this drawing style, we show how to draw an upward planar phylogenetic network with two slopes such that all leaves lie on a horizontal line.
Recommendations
Cites work
- 1-bend upward planar slope number of SP-digraphs
- A note on optimal area algorithms for upward drawings of binary trees
- Algorithms and Computation
- Algorithms for plane representations of acyclic digraphs
- Algorithms – ESA 2004
- Area requirement and symmetry display of planar upward drawings
- Bounded-degree graphs can have arbitrarily large slope numbers
- Building Blocks of Upward Planar Digraphs
- Depth-First Search and Linear Graph Algorithms
- Drawability of Complete Graphs Using a Minimal Slope Set
- Drawing Cubic Graphs with the Four Basic Slopes
- Drawing Graphs with Few Arcs
- Drawing Ordered (k − 1)–Ary Trees on k–Grids
- Drawing orders with few slopes
- Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles
- Drawing subcubic planar graphs with four slopes and optimal angular resolution
- Drawing unordered trees on \(k\)-grids
- Drawings of planar graphs with few slopes and segments
- scientific article; zbMATH DE number 2123123 (Why is no real title available?)
- scientific article; zbMATH DE number 2080085 (Why is no real title available?)
- scientific article; zbMATH DE number 2080088 (Why is no real title available?)
- Lattice diagrams with few slopes
- Level-planar drawings with few slopes
- On Embedding a Graph in the Grid with the Minimum Number of Bends
- On the complexity of orthogonal compaction
- On the complexity of the planar slope number problem
- On the computational complexity of upward and rectilinear planarity testing
- Optimal Upward Planarity Testing of Single-Source Digraphs
- Orthogonal Drawings of Plane Graphs Without Bends
- Outerplanar graph drawings with few slopes
- Phylogeny. Discrete and random processes in evolution
- Planar and plane slope number of partial 2-trees
- The complexity of bendless three-dimensional orthogonal graph drawing
- The planar slope number of planar partial 3-trees of bounded degree
- Tree Drawings on the Hexagonal Grid
- TWO FIXED-PARAMETER TRACTABLE ALGORITHMS FOR TESTING UPWARD PLANARITY
- Universal slope sets for upward planar drawings
- Upward drawings of triconnected digraphs.
- Upward planar drawings with three and more slopes
- Upward spirality and upward planarity testing
Cited in
(6)- Upward planar drawings with three and more slopes
- scientific article; zbMATH DE number 1554931 (Why is no real title available?)
- Upward Planar Drawings with Three and More Slopes
- Upward planar morphs
- Universal slope sets for upward planar drawings
- Visualizing multispecies coalescent trees: drawing gene trees inside species trees
This page was built for publication: Upward planar drawings with two slopes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5084713)
