Crossing Minimization for Symmetries

Buchheim, Christoph and Hong, Seok-Hee (2005) Crossing Minimization for Symmetries. [Journal (Paginated)]

This is the latest version of this item.

Full text not available from this repository.

Abstract

We consider the problem of drawing a graph with a given symmetry such that the number of edge crossings is minimal. We show that this problem is NP-hard, even if the order of orbits around the rotation center or along the reflection axis is fixed. We devise an $O(m\log m)$ algorithm for computing a crossing minimal drawing if inter-orbit edges may not cross orbits, showing in particular that intra-orbit edges do not contribute to the NP-hardness of the crossing minimization problem for symmetries.

Item Type:Journal (Paginated)
Additional Information:10.1007/s00224-005-1142-5
Keywords:symmetric drawings, planarity, crossing minimization
Classifications:G Algorithms and Complexity > G.910 Symmetries
G Algorithms and Complexity > G.420 Crossings
P Styles > P.780 Symmetric
ID Code:608

Available Versions of this Item

Repository Staff Only: item control page

References

D.Abelson, S.Hong, and D.Taylor.A group-theoretic method for drawing graphs symmetrically.Technical Report IT-IVG-2002-01, University of Sydney, 2002.

C.Buchheim and M.Jünger. Detecting symmetries by branch & cut. Mathematical Programming, Series B, 98:369-384, 2003.

H. Carr and W. Kocay. An algorithm for drawing a graph symmetrically. Bulletin of the ICA, 27:19-25, 1999.

R. Cimikowski. Algorithms for the fixed linear crossing number problem. Discrete Applied Mathematics, 122(1-3):93-115, 2002.

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

P. Eades and X. Lin. Spring algorithms and symmetry. Theoretical Computer Science, 240(2):379-405, 2000.

H. de Fraysseix. An heuristic for graph symmetry detection. In J. Kratochvil, editor, Graph Drawing 1999, volume 1731 of Lecture Notes in Computer Science, pages 276-285. Springer-Verlag, 1999.

M. Garey and D. Johnson. Computers and Intractability - A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.

M. Garey and D. Johnson. Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods, 4:312-316, 1983.

S. Hong. Drawing graphs symmetrically in three dimensions. In P. Mutzel, M. Jünger, and S. Leipert, editors, Graph Drawing 2001, volume 2265 of Lecture Notes in Computer Science, pages 189-204. Springer-Verlag, 2001.

S. Hong and P. Eades. A linear time algorithm for constructing maximally symmetric straight line drawings of planar graphs. In Graph Drawing 2004. To appear.

S. Hong and P. Eades. Drawing planar graphs symmetrically II: Biconnected graphs. Technical Report CS-IVG-2001-01, University of Sydney, 2001. To appear in Algorithmica.

S. Hong and P. Eades. Drawing planar graphs symmetrically III: Oneconnected graphs. Technical Report CS-IVG-2001-02, University of Sydney, 2001. To appear in Algorithmica.

S. Hong and P. Eades. Drawing planar graphs symmetrically IV: Disconnected graphs. Technical Report CS-IVG-2001-03, University of Sydney, 2001.

S. Hong and P. Eades. Symmetric layout of disconnected graphs. In T. Ibaraki, N. Katoh, and H. Ono, editors, ISAAC 2003, volume 2906 of Lecture Notes in Computer Science, pages 405-414. Springer-Verlag, 2003.

S. Hong, B. McKay, and P. Eades. Symmetric drawings of triconnected planar graphs. In SODA 2002, pages 356-365, 2002.

S. Hong, B. McKay, and P. Eades. A linear time algorithm for constructing maximally symmetric drawings of triconnected planar graphs. Technical Report IT-IVG-2004-01, University of Sydney, 2004.

S. Horton. The optimal linear arrangement problem: Algorithms and approximation. PhD thesis, Georgia Institute of Technology, 1997.

J. Manning. Geometric Symmetry in Graphs. PhD thesis, Purdue University, 1990.

S. Masuda, K. Nakajima, T. Kashiwabara, and T. Fujisawa. Crossing minimization in linear embeddings of graphs. IEEE Transactions on Computers, 39(1):124-127, 1990.

H. Purchase. Which aesthetic has the greatest effect on human understanding? In G. Di Battista}, editor, Graph Drawing '97, volume 1353 of Lecture Notes in Computer Science, pages 248-261. Springer-Verlag, 1997.

I. Vrt'o. Crossing numbers of graphs: A bibliography. www.ifi.savba.sk/~imrich