Directed Edge Constraints

As previously discussed, the standard convention for drawing directed edges in a graph is that they all point in the same direction, usually downwards. The IPSep-CoLa layout algorithm supports this convention since separation constraints in the vertical dimension can be used to require that each source vertex be above the destination vertex. Directed edge constraints are created for each directed edge by generating a separation constraint in the vertical dimension that places the source vertex above the destination vertex. When placing

Figure: A basic graph, with a cycle shown with purple dashed edges.

l250pt

directed edge constraints onto a graph, the presence of directed cycles must be considered, as it has been shown that a layout algorithm cannot know which node to place higher in the final layout. More specifically, having directed edge constraints placed upon vertices in directed cycles will cause the IPSep-CoLa algorithm to iterate over unsatisfiable constraints, because it is unable to solve the problem of which vertex to place higher in the vertical dimension. Because directed cycles are created by the ability for one vertex to have a directed path back to itself, every edge involved in a cycle causing path is termed a cyclic edge.

Consider the simple example in Fig . It contains one directed cycle that must be considered when directed edge constraints are generated for the final layout. This can be achieved by reducing the number of directed edge constraints on the portions of the graph that contain cycles. One possible solution, termed No Cycle Constraints, deals with directed cycles in a graph by not generating separation constraints for each edge involved in a directed cycle. This approach allows the layout algorithm to maximise its ability to relax the criteria regarding the direction of the cyclic edges in the final layout. Using the No Cycle Constraints method has the potential to result in a final layout that would be the same as if the cyclic edges were not directed edges at all, which may be preferable by the user given the context of the graph. An example of this approach is shown in .

The more conventional approach termed Acyclic Subgraph is to ``remove'' a single edge from the cycle. This approach is taken by Sugiyama et al in [8]. In that algorithm, the cycle is broken by reversing an edges direction in the final layout. However this may imply incorrect information to the reader about the structural properties of the graph. Using the Acyclic Subgraph approach with IPSep-CoLa allows directed edge constraints to be placed onto the vertices with a directed edge between them in the graph, except for the edge that has been ``removed'' to break the cycle. This then allows the algorithm to enforce the aesthetic criteria for directed edges as much as is possible. Depending on the context in which the graph is being drawn, this may be preferable as the majority of the vertices connected by directed edges will have directed edge constraints placed upon them, as shown in . More examples are shown later in Chapter .

The Acyclic Subgraph method has the advantage of preserving the majority of the directional information in the graph. However a problem that arises concerns the question of which edge to ``remove'' from the graph to break a directed cycle. A heuristic has already been shown by Bastert et al in [17] that provides an algorithm that approximates the maximum acyclic subgraph of $G$ . An example of breaking directed cycles by finding the maximum acyclic subgraph using their algorithm is shown in Fig . While the algorithm breaks the cycle, it is an $NP$ Hard problem to solve[14,19], and the algorithm makes arbitrary decisions about which edge to remove from the cycle. The arbitrary choice consequently does not guarantee a unique subgraph, and may erroneously cause a viewer of the graph to think something is special about the ``broken'' edge. This can also potentially introduce extra structural information about the graph into the final layout, that conveys false information to the reader.

Figure: () contains a graph laid out with IPSep-CoLa with no directed edge constraints placed upon the cyclic edges, () is the same graph with directed edge constraints. The cycles are highlighted in dashed edges and are coloured purple. Edges without constraints are in dashed red (all the cyclic edges in , and the upward pointing edge in ). Arguments could be made as to why both layouts can be considered good layouts depending on the context of the graph.

[] []

The No Cycle Constraints method requires a way to identify all the cyclic edges in a graph so that it doesn't generate a directed edge constraint for that edge. It would also be useful for a user to be shown all the cyclic edges by the tool if the user wants to assert control over which edge not to receive a directed edge constraint for the Acyclic Subgraph method. Therefore it is first necessary to determine all the directed edges in the graph that are part of a directed cycle. Using depth first search it is trivial to detect which vertices are in a cycle as shown in [21,11], however, no algorithm to the author's knowledge has been found to return the set of all directed edges involved in a cycle. This is an important distinction. Consider the graph in Fig . Vertex 4 is involved in two cycles by two different paths, therefore merely determining the fact that 4 is part of a cycle doesn't provide enough information, mainly, the set of directed edges involved in those cycle causing paths. To compound the problem, vertex 9 is part of a directed cycle containing vertices $\{9, 10, 6\}$ , but the edge $(9,11)$ isn't cyclic, so identifying vertex 9 as part of a cycle does not achieve the goal of returning the set of all cyclic edges.

Figure: () contains a graph with a cycle highlighted with purple dashed edges, () and () show that the maximum acyclic subgraph algorithm does not produce unique graphs as it chooses an arbitrary edge to remove.

[] [] []

Figure: A graph containing nested cycles highlighted with purple dashed edges.

A naïve approach is to say that all edges between two vertices that are part of cycles must be cyclic, however as the edge $(0,5)$ shows, that particular approach is not correct as the edge $(0,5)$ is clearly not part of a directed cycle, even though vertices 0, and 5 are part of directed cycles themselves. These examples show that the adaptation of algorithms that return the vertices involved in cycles is not a sufficient solution. The next chapter deals with this problem by putting forward an algorithm that identifies the set of all directed edges involved in a cycle.