On 3-Layer Crossings and Pseudo Arrangements

Shahrokhi, Farhad and Vrt'o, Imrich (1999) On 3-Layer Crossings and Pseudo Arrangements. In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999, Štirín Castle, Czech Republic , pp. 225-231 (Official URL: http://dx.doi.org/10.1007/3-540-46648-7_23).

Full text not available from this repository.

Abstract

Let G = (V_0, V_1, V_2, E) be a 3-layer drawings of G in which V_0, V_1, and V_2 are placed on 3 parallel lines and each edge in E is drawn using one straight line segment, are studied. A generalization of the linear arrangement problem which we call the 3-layer pseudo linear arrangement problem is introduced, and it is shown to be closely related to the 3-layer crossing number of G plus the sum of the square of degrees asymptotically has the same order of magnitude as the optimal solution to the 3-layer linear arrangement problem. Consequently, when G satisfies certain (reasonable) assumptions, we derive the first polynomial time approximation algorithm to compute the 3-layer crossing number within a multiplicative factor of O(log n) from the optimal.

Item Type:Conference Paper
Additional Information:10.1007/3-540-46648-7_23
Classifications:M Methods > M.500 Layered
G Algorithms and Complexity > G.700 Layering
P Styles > P.720 Straight-line
G Algorithms and Complexity > G.420 Crossings
P Styles > P.480 Layered
ID Code:323

Repository Staff Only: item control page

References

Catarci, T.: The assignment heuristics for crossing reduction. IEEE Transactions on Systems, Man and Cybernetics 25 (1995) 515-521

Chung, F. R. K.: On optimal linear arrangements of trees. Computers and Mathematics with Applications 10 (1984) 43-60

Díaz, J.: Graph layout problems. In International Symposium on Mathematical Foundations of Computer Sciences. Lecture Notes in Computer Science, Vol. 629. Springer-Verlag, Berlin Heidelberg New York (1992) 14-21

Di Battista, J., Eades, P., Tamassia, R., Tollis, I. G.: Algorithms for drawing graphs: an annotated bibliography. Computational Geometry 4 (1994) 235-282

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

Eades, P., Whitesides, S.: Drawing graphs in 2 layers. Theoretical Computer Science 131 (1994) 361-374

Even, G., Naor, J. S., Rao, S., Schieber, B.: Divide-and-Conquer approximation algorithms via spreading matrices. in 36th Annual IEEE Symposium on Foundation of Computer Science. IEEE Computer Society Press (1995) 62-71

Even, G., Naor, J. S., Rao, S., Schieber, B.: Fast approximate graph partition algorithms. In 8th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM Press (1997) 639-648

Garey, M. R., Johnson, D.S.: Crossing number is NP-complete. SIAM J. Algebraic and Discrete Methods 4 (1983) 312-316

Hansen, M.: Approximate algorithms for geometric embeddigns in the plane with applications to parallel processing problems. In 30th Annual IEEE Symposium on Foundation of Computer Science. IEEE Computer Society Press (1989) 604-609

Jünger, M., Mutzel, P.: Exact and heuristic algorithm for 2-layer straight line crossing number. In 3rd Symposium on Graph Drawing '95. Lecture Notes in Computer Science, Vol. 1027. Springer-Verlag, Berlin Heidelberg New York (1996) 337-348

Jünger, M., Lee, E. K., Mutzel P., Odenthal T.: A polyhedral approach to the multi-layer crossing number problem. In 5th Symposium on Graph Drawing '97. Lecture Notes in Computer Science, Vol. 1353. Springer-Verlag, Berlin Heidelberg New York (1997) 13-24

Leighton, F. T.: Complexity issues in VLSI. MIT Press, Massachusetts (1983)

May, M., Szkatula, K.: On the bipartite crossing number. Control and Cybernetics 17 (1988) 85-98

Mutzel, P.: An alternative method to crossing minimization on hierarchical graphs. In 4th Symposium on Graph Drawing '96. Lecture Notes in Computer Science, Vol. 1190. Springer-Verlag, Berlin Heidelberg New York (1997) 318-333

Pach, J., Agarwal, K.: Combinatorial Geometry. John Wiley & Sons Inc., New York (1995)

Purchase, H.: Which aesthetics has the greatest effect on human understanding? In 5th Symposium on Graph Drawing '97. Lecture Notes in Computer Science, Vol. 1353. Springer-Verlag, Berlin Heidelberg New York (1997) 248-261

Rao, S., Richa, A.:, New approximation techniques for some ordering problems. In: 9th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM Press (1998) 211-225

Sharokhi, F., Sýkora, O., Székely, L. A., Vrt'o, I.: On bipartite crossings, largest biplanar subgraphs, and the linear arrangement problem. In Workshop on Algorithms and Data Structures '97. Lecture Notes in Computer Science, Vol. 1272. Springer-Verlag, Berlin Heidelberg New York (1997) 55-68 Extended version will appear in SIAM Journal on Computing as: On bipartite drawings and the linear arrangement problem

Shahrokhi, F., Sýkora, O., Székely, L. A., and Vrt'o, I.: Crossing number problems: bounds and applications. In: Bárány, I., and Böröczky, K. (eds): Intuitive Geometry. Bolyai Society Mathematical Studies, Vol 6. Akadémia Kiadó, Budapest (1997) 179-206

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

Warfield, J.: Crossing theory and hierarchy mapping. IEEE Transactions on Systems, Man and Cybernetics 7 (1977) 502-523

White, A. T., and Beineke, L. W.: Topological graph theory. In: L. W. Beineke, L. W., and R. J. Wilson, R. J. (eds.): Selected Topics in Graph Theory. Academic Press, New York (1978) 15-50