A Practical Approach to Static Node Positioning

Luo, Junhui and Miriyala, Kanth (1995) A Practical Approach to Static Node Positioning. In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994, Princeton, New Jersey, USA , pp. 436-443 (Official URL: http://dx.doi.org/10.1007/3-540-58950-3_397).

Full text not available from this repository.

Abstract

This paper discusses how we adapted an algorithm by Kernighan and Lin and its refinement by Fiduccia and Mattheyses for network partitioning to get an efficient heuristic for aesthetically and statically laying out undirected graphs.

Item Type:Conference Paper
Additional Information:10.1007/3-540-58950-3_397
Classifications:M Methods > M.999 Others
G Algorithms and Complexity > G.560 Geometry
ID Code:255

Repository Staff Only: item control page

References

Fiduccia, C.M. and Mattheyses, R.M., A Linear-Time Heuristic for Improving Network Partitions, Proceedings of the 19th Design Automation Conference , IEEE 1982, pp. 175-181.

Miriyala, K. Hornick, S.W., and Tamassia, R, An Incremental Approach to Aesthetic Graph Layout, Proc. of 6th Intl. Workshop on Computer-Aided Software Engineering, 1993, pp. 297-308.

Naidu, B. and Miriyala, K., Space Creation and Compaction in Dynamic Diagramming, Andersen Consulting Internal Paper.

Kernighan, B.W. and Lin, S.: An Efficient Heuristic Procedure for Partitioning graphs, Bell System Technical Journal, Vol. 49, Feb. 1970, pp. 291-307.

Eades, P.: A Heuristic for Graph DRawing, Congressus Numerantium, Vol. 42, pp. 149-160, 1984.

Di Battista, Eades,P., and Tamassia, R.: Algorithms for Drawing Graphs: an Annotated bibliography, unpublished paper, March, 1993.

Fruchterman, T.M.J. and Reingold, E.M.: Graph Drawing by Force-Directed Placement, Software Practice and Experinece, Vol. 21, No. 11, pp. 1129-1164, 1991.

Tamassia, R., Di Battista, G., and Batini, C.: Automatic Graph Drawing and Readability of Diagrams, IEEE Trans. on Systems, Man, and Cybernetics, Vol. 18, No.1, pp. 61-79, 1988.

Kamada, T.: On Visualization of Abstract Objets and Relations, Ph.D. thesis, Department of Information Science, University of Tokyo, 1988.

Garey M., and Johnson D.: Computers and Intractability: a guide to the theory of NP-completeness, W. Freeman and Company, 1979.

Cai, J., Han,X., and Tarjan, R.E.,: An O(m log n)-time Algorithm for the Maximal Subgraph Problem, SIAM J. on Computing, 1993.

Batini, C., Nardelli, E., Talamo, M., and Tamassia, R.: A Graphtheoretic Approach to Aesthetic Layout of Information Systems Diagrams, Proc. 10th Intl. Workshop on Graphtheoretic Concepts in Computer Science (Berlin, June 1984), pp. 9-18, Trauner Verlag, 1984.