Nikola S. Nikolov
Abstract
We propose two fast heuristics for solving the NP-hard problem of graph layering with the minimum width and consideration of dummy nodes. Our heuristics can be used at the layer-assignment phase of the Sugiyama method for drawing of directed graphs. We evaluate our heuristics by comparing them to the widely used fast-layering algorithms in an extensive computational study with nearly 6000 input graphs. We also demonstrate how the well-known longest-path and Coffman--Graham algorithms can be used for finding narrow layerings with acceptable aesthetic properties.
- Ahmed, A., Dwyer, T., Forster, M., Fu, X., Ho, J., Hong, S., Koschützki, D., Murray, C., Nikolov, N. S., Taib, R., Tarassov, A., and Xu, K. 2005. GEOMI: GEOmetry for Maximum Insight. In Graph Drawing: Proceedings of 13th International Symposium, GD 2005, vol. 3843 of Lecture Notes in Computer Science. Springer-Verlag, New York. 468--479. Google Scholar
Digital Library
- Branke, J., Eades, P., Leppert, S., and Middendorf, M. 2001. Width restricted layering of acyclic digraphs with consideration of dummy nodes. Tech. Rep. No. 403, Intitute AIFB, University of Karlsruhe, 76128 Karlsruhe, Germany.Google Scholar
- Branke, J., Leppert, S., Middendorf, M., and Eades, P. 2002. Width-restricted layering of acyclic digraphs with consideration of dummy nodes. Information Processing Letters 81, 2, 59--63. Google ScholarDigital Library
- Carpano, M. J. 1980. Automatic display of hierarchized graphs for computer aided decision analysis. IEEE Transactions on Systems, Man and Cybernetics 10, 11, 705--715.Google ScholarCross Ref
- Coffman, E. G. and Graham, R. L. 1972. Optimal scheduling for two processor systems. Acta Informatica 1, 200--213.Google ScholarDigital Library
- Di Battista, G., Englewood Cliffs, N. J., Garg, A., Liotta, G., Tamassia, R., Tassinari, E., and Vargiu, F. 1997. An experimental comparison of four graph drawing algorithms. Computational Geometry: Theory and Applications 7, 303--316. Google ScholarDigital Library
- Di Battista, G., Eades, P., Tamassia, R., and Tollis, I. G. 1999. Graph drawing. Prentice Hall.Google Scholar
- Eades, P., Lin, X., and Smyth, W. F. 1993. A fast and effective heuristic for the feedback arc set problem. Information Processing Letters 47, 319--323. Google ScholarDigital Library
- Eades, P. and Sugiyama, K. 1990. How to draw a directed graph. Journal of Information Processing 13, 4, 424--437. Google ScholarDigital Library
- Gansner, E. R., Koutsofios, E., North, S. C., and Vo, K.-P. 1993. A technique for drawing directed graphs. IEEE Transactions on Software Engineering 19, 3, 214--230. Google ScholarDigital Library
- Healy, P. and Nikolov, N. S. 2002a. A branch-and-cut approach to the directed acyclic graph layering problem. In Graph Drawing: Proceedings of 10th International Symposium, GD 2002, vol. 2528 of Lecture Notes in Computer Science. Springer-Verlag, New York. 98--109. Google ScholarDigital Library
- Healy, P. and Nikolov, N. S. 2002b. How to layer a directed acyclic graph. In Graph Drawing: Proceedings of 9th International Symposium, GD 2001, vol. 2265 of Lecture Notes in Computer Science. Springer-Verlag, New York. 16--30. Google ScholarDigital Library
- Hu, T. 1961. Parallel sequencing and assembly line problems. Operations Research 9, 841--848.Google ScholarDigital Library
- Kwok, Y.-K. and Ahmad, I. 1999. Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Computing Surveys 31, 4, 406--471, 1999. Google ScholarDigital Library
- Lemke, I. 1994. Entwicklung and Implementierung eines Visualisierungswerkzeuges für Anwendungen im übersetzerbau. Diplomarbeit, Universität des Saarlandes, FB 14 Informatik.Google Scholar
- Mehlhorn, K. 1984. Data Structures and Algorithms, Volume 2: Graph Algorithms and NP-Completeness. Springer-Verlag, New York. Google ScholarDigital Library
- Nemhauser, G. L. and Wolsey, L. A. 1988. Integer and Combinatorial Optimization. Wiley, New York. Google ScholarDigital Library
- Nikolov, N. S. and Tarassov, A. 2006. Graph layering by promotion of nodes. Discrete Applied Mathematics, Special Issue Associated with the IV ALIO/EURO Workshop on Applied Combinatorial Optimization. 154, 5, 848--860. Google ScholarDigital Library
- Sugiyama, K. and Misue, K. 1995. Graph drawing by the magneting spring model. Journal of Visual Languages and Computing 6, 3, 217--231.Google ScholarCross Ref
- Sugiyama, K., Tagawa, S., and Toda, M. 1981. Methods for visual understanding of hierarchical system structures. IEEE Transaction on Systems, Man, and Cybernetics 11, 2, 109--125.Google ScholarCross Ref
- Tarassov, A., Nikolov, N. S., and Branke, J. 2004. A heuristic for minimum-width of graph layering with consideration of dummy nodes. In Experimental and Efficient Algorithms, Third International Workshop, WEA 2004, vol. 3059 of Lecture Notes in Computer Science. Springer-Verlag, New York. 570--583.Google Scholar
- Ulman, J. 1975. NP-complete scheduling problems. Journal of Computer and System Sciences 10, 384--393.Google ScholarDigital Library
- Utech, J., Branke, J., Schmeck, H., and Eades, P. 1998. An evolutionary algorithm for drawing directed graphs. In Proceedings of the 1998 International Conference on Imaging Science, Systems, and Technology (CISST' 98). 154--160.Google Scholar
- Warfield, J. N. 1977. Crossing theory and hierarchy mapping. IEEE Transactions on Systems, Man and Cybernetics 7, 7, 502--523.Google ScholarCross Ref
Index Terms
- In search for efficient heuristics for minimum-width graph layering with consideration of dummy nodes
Recommendations
Graph layering by promotion of nodes
Special issue: IV ALIO/EURO workshop on applied combinatorial optimizationThis work contributes to the wide research area of visualization of hierarchical graphs. We present a new polynomial-time heuristic which can be integrated into the Sugiyama method for drawing hierarchical graphs. Our heuristic, which we call Promote ...
Competitive Algorithms for Layered Graph Traversal
A layered graph is a connected graph whose vertices are partitioned into sets L0=s, L1, L2,..., and whose edges, which have nonnegative integral weights, run between consecutive layers. Its width is $\max\{|L_i|\}$. In the on-line layered graph traversal ...
Queue Layouts, Tree-Width, and Three-Dimensional Graph Drawing
FST TCS '02: Proceedings of the 22nd Conference Kanpur on Foundations of Software Technology and Theoretical Computer ScienceA three-dimensional (straight-line grid) drawing of a graph represents the vertices by points in Z 3 and the edges by noncrossing line segments. This research is motivated by the following open problem due to Felsner, Liotta, and Wismath [Graph Drawing '...
Reviews
Hao Wang
The visualization of graphs and networks has many applications, such as class hierarchies in software engineering, entity-relationship (ER) diagrams in database systems, and program evaluation and review technique (PERT) diagrams in project management. Since in many of those applications it is necessary to describe a hierarchical relationship between objects, directed acyclic graphs are widely used. The Sugiyama method [1] is a standard method for hierarchical graph drawing, and has received much research attention. This method consists of three phases. In the first phase, the set of nodes is partitioned into subsets with integer ranks, such that nodes connected by a directed path belong to different subsets, and the tail of every edge has a higher rank than its tip. Such an ordered partition of the node set is called a layering. If the width of the drawing is required to be minimal, then the layering is called minimum-width graph layering, which is known to be nondeterministic polynomial time hard (NP-hard) when the dummy nodes are also taken into account. The second phase of the Sugiyama method arranges the nodes within every level in a proper order; the last phase gives x and y coordinates to all nodes and draws all directed edges. In this paper, two heuristic algorithms that provide fast-layering methods are presented, together with a computational comparison of other known layering techniques. The authors provide the details of five layering algorithms, and test their results and efficiency by using a relatively large dataset of directed acyclic graphs, introduced by Di Battista et al. [2]. Although the two new heuristics are not more efficient than the other algorithms, one of them, MinWidth, provides the ability to find a layering with a smaller width, and the behavior of the other, StretchWidth, seems to be similar to the longest path layering algorithm. In conclusion, the authors present a good survey of fast-layering algorithms, by comparing five different methods. Because graph drawing has many applications, the results of this paper can be used in many other related problems and areas. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments