Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Three Approaches to 3D-Orthogonal Box-Drawings
Extended Abstract
| Book Series | Lecture Notes in Computer Science |
| Publisher | Springer Berlin / Heidelberg |
| ISSN | 0302-9743 (Print) 1611-3349 (Online) |
| Volume | Volume 1547/1998 |
| Book | Graph Drawing |
| DOI | 10.1007/3-540-37623-2 |
| Copyright | 1998 |
| ISBN | 978-3-540-65473-5 |
| DOI | 10.1007/3-540-37623-2_3 |
| Pages | 30-43 |
| Subject Collection | Computer Science |
| SpringerLink Date | Thursday, January 01, 1998 |
| |
|
Three Approaches to 3D-Orthogonal Box-Drawings
Extended Abstract
Therese C. Biedl5 
| (5) |
McGill University, 3480 University St. #318, Montréal, Qc, H3A 2A7, Canada |
Abstract
In this paper, we study orthogonal graph drawings in three dimensions with nodes drawn as boxes. The algorithms that we present
can be differentiated as resulting from three different approaches to creating 3D-drawings; we call these approaches edge-lifting,
half-edge-lifting, and three-phase-method.
Let G be a graph with n vertices, m edges, and maximum degree Δ. We obtain a drawing of G in an n × n × Δ-grid where the surface area of the box of a node v is O(deg(v)); this improves significantly on previous results. We also consider drawings with at most one node per grid-plane, and exhibit
constructions in an n × n × m-grid and a lower bound of Ω(m
2); hence upper and lower bounds match for graphs with θ(n
2) edges.
These results were part of a PhD thesis at Rutgers University under the supervision of Prof. Endre Boros, and done, in part,
while the author was working at Tom Sawyer Software and funded by the NIST under grant number 70NANB5H1162. Patent on these
and related results is pending.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|