Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
Medientyp:
E-Artikel;
Sonstige Veröffentlichung
Titel:
Crossing Minimization for Symmetries (Extended Abstract)
Beteiligte:
Buchheim, Christoph
[Verfasser:in];
Hong, Seok-Hee
[Verfasser:in]
Erschienen:
Springer, 2002
Sprache:
Deutsch;
Englisch
Entstehung:
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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.