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 1820, 1996 , pp. 318333(Official URL: http://dx.doi.org/10.1007/3540624953_57). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540624953_57
AbstractA 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 klevel planar. For the final diagram the removed edges are reinserted into a klevel planar drawing. Hence, instead of considering the klevel crossing minimization problem, we suggest solving the klevel 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 2level planar subgraph of maximum weight in a given 2level graph. This problem is nphard. Based on characterization of 2level planar graphs, we give an integer linear programming formulation for the 2level planarization problem. Moreover, we define and investigate the polytope 2LPS(G) associated with the set of all 2level planar subgraphs of a given 2level graph G. We will see that this polytope has full dimensionand and that the inqualities occuring in the integer linear description are facetdefining 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 2level planarization problem. Furthermore, we derive new inqualities that substantially improve the quality of the obtained solution. We report on first computational results.
Actions (login required)
