English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

An alternative method to crossing minimization on hierarchical graphs

MPS-Authors
/persons/resource/persons45092

Mutzel,  Petra
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

MPI-I-97-1-008.pdf
(Any fulltext), 263KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Mutzel, P.(1997). An alternative method to crossing minimization on hierarchical graphs (MPI-I-1997-1-008). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-9E22-8
Abstract
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 verti ces within the levels such that the number of crossings is minimized. We suggest an alternative method for the 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, i nstead of considering the $k$-level crossing minimization problem, we suggest solv ing the $k$-level planarization problem. In this paper we address the case $k=2$. First, we give a motivation for our appro ach. Then, we address the problem of extracting a 2-level planar subgraph of maximum we ight in a given 2-level graph. This problem is NP-hard. Based on a characterizatio n of 2-level planar graphs, we give an integer linear programming formulation for the 2-level planarization problem. Moreover, we define and investigate the polytop e $\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 dimension and that the i nequalities occuring in the integer linear description are facet-defining for $\2L PS(G)$. The inequalities in the integer linear programming formulation can be separated in polynomial time, hence they can be used efficiently in a branch-and-cut method fo r solving practical instances of the 2-level planarization problem. Furthermore, we derive new inequalities that substantially improve the quality of the obtained solution. We report on extensive computational results.