Fully Dynamic 3-Dimensional Orthogonal Graph Drawing
Journal of graph algorithms and applications, Tome 5 (2001) no. 2, pp. 1-34
Cet article a éte moissonné depuis la source Journal of Graph Algorythms and Applications website
In a 3-dimensional orthogonal drawing of a graph, vertices are mapped to grid points on a 3-dimensional rectangular integer lattice and edges are routed along integer grid lines. In this paper, we present a technique that produces a 3D orthogonal drawing of any graph with $n$ vertices of degree 6 or less, using at most 6 bends per edge route and in a volume bounded by $O(n^2)$. The advantage of our strategy over previous drawing methods is that our method is fully dynamic, allowing both insertion and deletion of vertices and edges, while maintaining the volume and bend bounds. The drawing can be obtained in $O(n)$ time and insertions/deletions are performed in $O(1)$ time. Multiple edges and self loops are permitted. Three related constructions are also presented: a more elaborate construction that uses only 5 bends per edge, a simpler, more balanced drawing that requires at most 7 bends per edge, and a technique for displaying directed graphs.
@article{JGAA_2001_5_2_a0,
author = {M. Closson and S. Gartshore and J. Johansen and S. Wismath},
title = {Fully {Dynamic} {3-Dimensional} {Orthogonal} {Graph} {Drawing}},
journal = {Journal of graph algorithms and applications},
pages = {1--34},
year = {2001},
volume = {5},
number = {2},
doi = {10.7155/jgaa.00033},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00033/}
}
TY - JOUR AU - M. Closson AU - S. Gartshore AU - J. Johansen AU - S. Wismath TI - Fully Dynamic 3-Dimensional Orthogonal Graph Drawing JO - Journal of graph algorithms and applications PY - 2001 SP - 1 EP - 34 VL - 5 IS - 2 UR - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00033/ DO - 10.7155/jgaa.00033 LA - en ID - JGAA_2001_5_2_a0 ER -
%0 Journal Article %A M. Closson %A S. Gartshore %A J. Johansen %A S. Wismath %T Fully Dynamic 3-Dimensional Orthogonal Graph Drawing %J Journal of graph algorithms and applications %D 2001 %P 1-34 %V 5 %N 2 %U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00033/ %R 10.7155/jgaa.00033 %G en %F JGAA_2001_5_2_a0
M. Closson; S. Gartshore; J. Johansen; S. Wismath. Fully Dynamic 3-Dimensional Orthogonal Graph Drawing. Journal of graph algorithms and applications, Tome 5 (2001) no. 2, pp. 1-34. doi: 10.7155/jgaa.00033
Cité par Sources :