Buchheim, Christoph and Hong, Seok-Hee (2002) Crossing Minimization for Symmetries. [Conference Paper]
 | There is a more recent version of this eprint available. Click here to view it. |
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. Nevertheless, there is a linear time algorithm to test planarity and to construct a planar embedding if possible. Finally, 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. From this result, we can derive an O(m log m) crossing minimization algorithm for symmetries with an orbit graph that is a path.
| Item Type: | Conference Paper |
|---|---|
| Additional Information: | Lecture Notes in Computer Science 2518 |
| 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: | 534 |
| Deposited By: | Buchheim, Christoph |
| Deposited On: | 07 Apr 2005 |
| Last Modified: | 18 Sep 2008 13:08 |
| Alternative Locations: | http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2518&spage=563 |
Available Versions of this Item
- Crossing Minimization for Symmetries. (deposited 07 Apr 2005) [Currently Displayed]
Repository Staff Only: item control page
