|
Description: |
> |
The NP-hard problem of finding symmetries in an abstract graph plays
an important role in automatic graph drawing and other
applications. We developed an exact algorithm for automorphism and
symmetry detection based on the branch & cut technique. Furthermore,
we extended our approach to fuzzy symmetries: we allow to delete or
create edges temporarily and search for a minimum number of edges
that have to be deleted or created such that the resulting graph
admits a symmetry of given order.
The second step of symmetric graph drawing is to realize the detected
(abstract) symmetries by nice drawings of the graph. In our project,
we examined the crossing minimization problem: given an automorphism
of a graph, find a crossing-minimal drawing displaying this
automorphism as a two-dimensional symmetry, if there is one. We
showed that several restricted versions of this problem are NP-hard,
while there is an O(m log m) algorithm for the case that 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. Finally, we showed that a
symmetry can be tested for planarity in linear time, using the
SPQR-tree data structure.
|
|
