Volume requirements of 3D upward drawings
type: Item
instance of: scholarly article
title: Volume requirements of 3D upward drawings
zbMATH Open document ID: 1182.05087
author: Giuseppe Liotta
author: S. Wismath
author: Emilio Di Giacomo
author: Henk Meijer
published in: Discrete Mathematics
publication date: 2009-04-09T00:00:00Z
review text: The authors study \textit{upward 3D drawing} of directed acyclic graphs which is realization of the embedding of such graphs into the simple cubic lattice so that the edges are straight-line segments and are oriented in a common direction. They show that there exists a family of outerplanar directed acyclic graphs which require \(\Omega (n^{1.5})\) volume. It is also shown that directed trees admit linear volume, that is, they can be drawn on a grid of size \(O(1) \times O(1) \times O(n)\).
reviewed by: Youngsik Huh
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5542412
zbMATH Keywords: graph drawing
zbMATH Keywords: directed acyclic graph
Wikidata QID: Q62042552
MaRDI profile type: Publication
full work available at URL: j.disc.2007.12.061
OpenAlex ID: W2051202422
cites work: 3D straight-line grid drawing of 4-colorable graphs
cites work: Three-dimensional graph drawing
cites work: Graph Drawing
cites work: Computing straight-line 3D grid drawings of graphs in linear volume
cites work: Layout of Graphs with Bounded Tree-Width
cites work: Q4657578
cites work: Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
cites work: The Maximum Number of Edges in a Three-Dimensional Grid-Drawing
cites work: Upward drawings of triconnected digraphs.
cites work: Optimal Upward Planarity Testing of Single-Source Digraphs
cites work: On the computational complexity of upward and rectilinear planarity testing
cites work: Upward Planar Drawing of Single-Source Acyclic Digraphs
cites work: Q4667621
cites work: Q5387656
cites work: Area requirement and symmetry display of planar upward drawings
cites work: Stack and Queue Layouts of Posets
cites work: Stack and Queue Layouts of Directed Acyclic Graphs: Part II
cites work: Stack and Queue Layouts of Directed Acyclic Graphs: Part I
cites work: Efficient Coroutine Generation of Constrained Gray Sequences
cites work: Upward three-dimensional grid drawings of graphs
DOI: 10.1016/J.DISC.2007.12.061
description: scientific article; zbMATH DE number 5542412