The Vertex-Exchange Graph: A New Concept for Multi-level Crossing Minimisation

Healy, Patrick and Kuusik, Ago (1999) The Vertex-Exchange Graph: A New Concept for Multi-level Crossing Minimisation. In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999, Štirín Castle, Czech Republic , pp. 205-216 (Official URL: http://dx.doi.org/10.1007/3-540-46648-7_21).

Full text not available from this repository.

Abstract

In this paper we consider the problems of testing a multi-level graph for planarity and laying out a multi-level graph. We introduce a new abstraction that we call a vertex-exchange graph. We demonstrate how this concept can be used to solve these problems by providing clear and simple algorithms for testing a multi-level graph for planarity and laying out a multi-level graph when planar. We also show how the concept can be used to solve other problems relating to multi-level graph layout.

Item Type:Conference Paper
Additional Information:10.1007/3-540-46648-7_21
Classifications:M Methods > M.999 Others
G Algorithms and Complexity > G.999 Others
M Methods > M.600 Planar
G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.770 Planarity Testing
P Styles > P.999 Others
P Styles > P.540 Planar
ID Code:329

Repository Staff Only: item control page

References

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing, Algorithms for the Visualization of Graphs. Prentice Hall, 1999.

P. Eades and D. Kelly. Heuristics for drawing 2-layered networks. Ars Combinatoria, 21-A:89-98. 1986.

P. Eades and K. Sugiyama. How to draw a directed graph. Journal of Information Processing, 13(4):424-437, 1990.

P. Eades and N. C. Wormald. Edge crossings in drawings of bipartite graphs. Algorithmica, 11:379-403, 1994.

P. Healy and A. Kuusik. Characterisation of level non-planar graphs by minimal patterns. Technical Report UL-CSIS-98-4, University of Limerick, 1998.

M. Jünger, E. K. Lee, P. Mutzel, and T. Odenthal. A polyhedral approach to multi-layer crossing minimization problem. In Graph Drawing, 5th International Symposium, GD'97, Rome, Italy, September 1997, volume 1353 of Lecture Notes in Computer Science, pages 13-24. Springer-Verlag, 1997.

M. Jünger and P. Mutzel. Exact and heuristic algorithm for 2-layer crossing minimization. In Graph Drawing, Symposium on Graph Drawing, GD'95. Passau, Germany, September 20-22, 1995, volume 1027 of Lecture Notes in Computer Science, pages 337-348. Springer-Verlag, 1995.

S. Leipert. Level planarity testing and embedding in linear time. PhD thesis, Institut für Informatik, Universität zu Köln, 1998.

K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man, and Cybernetics, 11(2):109-125, 1981.

J. Utech, J. Branke, H. Schmeck, and P. Eades. An evolutionary algorithm for drawing directed graphs. In Proceedings of the 1998 International Conference on Imaging Science, Systems, and Technology (CISST'98), pages 154-160, 1998.