Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-I-97-1-008

An alternative method to crossing minimization on hierarchical graphs

Mutzel, Petra

MPI-I-97-1-008. March 1997, 15 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.


Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-97-1-008.ps328 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1997-1-008

Hide details for BibTeXBibTeX
@TECHREPORT{Mutzel97,
  AUTHOR = {Mutzel, Petra},
  TITLE = {An alternative method to crossing minimization on hierarchical graphs},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-97-1-008},
  MONTH = {March},
  YEAR = {1997},
  ISSN = {0946-011X},
}