An Alternative Method to Crossing Minimization on Hierarchical Graphs (extended abstract)

Mutzel, Petra (1997) An Alternative Method to Crossing Minimization on Hierarchical Graphs (extended abstract). In: Symposium on Graph Drawing, GD '96, September 18-20, 1996 , pp. 318-333(Official URL:

Full text not available from this repository.


A common method for drawing directed graphs is, as a first step, to partition the vertices into a set of k levels and then, as a second step, to permute the vertices within the levels such that number of crossings is minimized. We suggest an alternative method for second step, namely, removing the minimal number of edges such that the resulting graph is k-level planar. For the final diagram the removed edges are reinserted into a k-level planar drawing. Hence, instead of considering the k-level crossing minimization problem, we suggest solving the k-level planarization problem. In this paper we adress the case k=2. First, we give a motivation for our approach. Then, we adress the problem of extracting a 2-level planar subgraph of maximum weight in a given 2-level graph. This problem is np-hard. Based on characterization of 2-level planar graphs, we give an integer linear programming formulation for the 2-level planarization problem. Moreover, we define and investigate the polytope 2LPS(G) associated with the set of all 2-level planar subgraphs of a given 2-level graph G. We will see that this polytope has full dimensionand and that the inqualities occuring in the integer linear description are facet-defining for 2LPS(G). The inqualities in the integer linear programming formulation can be separated in polynomial time, hence they can be used efficiently in a cutting plane method for solving practical instances of the 2-level planarization problem. Furthermore, we derive new inqualities that substantially improve the quality of the obtained solution. We report on first computational results.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-62495-3_57
Classifications: M Methods > M.500 Layered
G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.420 Crossings
P Styles > P.480 Layered

Actions (login required)

View Item View Item