## Crossing Minimisation

### Extended Level Graphs Crossing Minimisation

 C. Bachmaier, H. Buchner, M. Forster and S. Hong, "Crossing minimization in Extended Level Drawings of Graphs", Discrete Applied Mathematics, 158(3), pp. 159-179, 2010, Elsevier. The most popular method of drawing directed graphs is to place vertices on a set of horizontal or concentric levels, known as level drawings. Level drawings are well studied in Graph Drawing due to their strong application for the visualization of hierarchy in graphs. There are two drawing conventions: Horizontal drawings use a set of parallel lines and radial drawings use a set of concentric circles. In level drawings, edges are only allowed between vertices on different levels. However, many real world graphs exhibit hierarchies with edges between vertices on the same level. In this paper, we initiate the new problem of extended level drawings of graphs, which was addressed as one of the open problems in social network visualization, in particular, displaying centrality values of actors. More specifically, we study minimizing the number of edge crossings in extended level drawings of graphs. The main problem can be formulated as the extended one-sided crossing minimization problem between two adjacent levels, as it is folklore with the one-sided crossing minimization problem in horizontal drawings. We first show that the extended one-sided crossing minimization problem is NP-hard for both horizontal and radial drawings, and then present efficient heuristics for minimizing edge crossings in extended level drawings. Our extensive experimental results show that our new methods reduce up to 30% of edge crossings.

### Symmetric Crossing Minimisation

 Christoph Buchheim, Seok-Hee Hong: Crossing Minimization for Symmetries. Theory Comput. Syst. 38(3): 293-311 (2005) 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 logm) algorithm for computing a crossing minimal drawing if inter-orbit edgesmaynot cross orbits, showing in particular that intra-orbit edges do not contribute to the NP-hardness of the crossing minimization problem for symmetries.