Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10328425 | Discrete Applied Mathematics | 2005 | 5 Pages |
Abstract
Some recent papers for three-dimensional orthogonal graph drawing use a technique introduced by Kolmogorov and Barzdin. This technique consists of assigning x-coordinates and y-coordinates, and then computing compatible z-coordinates, which was done via vertex-colouring a conflict graph. In this note, we show that compatible z-coordinates can also be found by edge-colouring a (different) conflict graph. As a consequence, the time complexity for computing the drawings decreases, and the volumes of the drawings are reduced as well.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Therese Biedl, Timothy M. Chan,