Radermacher, Marcel ;
Rutter, Ignaz
Geometric CrossingMinimization  A Scalable Randomized Approach
Abstract
We consider the minimization of edgecrossings in geometric drawings of graphs G=(V, E), i.e., in drawings where each edge is depicted as a line segment. The respective decision problem is NPhard [Daniel Bienstock, 1991]. Crossingminimization, in general, is a popular theoretical research topic; see Vrt'o [Imrich Vrt'o, 2014]. In contrast to theory and the topological setting, the geometric setting did not receive a lot of attention in practice. Prior work [Marcel Radermacher et al., 2018] is limited to the crossingminimization in geometric graphs with less than 200 edges. The described heuristics base on the primitive operation of moving a single vertex v to its crossingminimal position, i.e., the position in R^2 that minimizes the number of crossings on edges incident to v.
In this paper, we introduce a technique to speedup the computation by a factor of 20. This is necessary but not sufficient to cope with graphs with a few thousand edges. In order to handle larger graphs, we drop the condition that each vertex v has to be moved to its crossingminimal position and compute a position that is only optimal with respect to a small random subset of the edges. In our theoretical contribution, we consider drawings that contain for each edge uv in E and each position p in R^2 for v o(E) crossings. In this case, we prove that with a random subset of the edges of size Theta(k log k) the cocrossing number of a degreek vertex v, i.e., the number of edge pairs uv in E, e in E that do not cross, can be approximated by an arbitrary but fixed factor delta with high probability. In our experimental evaluation, we show that the randomized approach reduces the number of crossings in graphs with up to 13 000 edges considerably. The evaluation suggests that depending on the degreedistribution different strategies result in the fewest number of crossings.
BibTeX  Entry
@InProceedings{radermacher_et_al:LIPIcs:2019:11197,
author = {Marcel Radermacher and Ignaz Rutter},
title = {{Geometric CrossingMinimization  A Scalable Randomized Approach}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {76:176:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771245},
ISSN = {18688969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11197},
URN = {urn:nbn:de:0030drops111977},
doi = {10.4230/LIPIcs.ESA.2019.76},
annote = {Keywords: Geometric Crossing Minimization, Randomization, Approximation, VCDimension, Experiments}
}
06.09.2019
Keywords: 

Geometric Crossing Minimization, Randomization, Approximation, VCDimension, Experiments 
Seminar: 

27th Annual European Symposium on Algorithms (ESA 2019)

Issue date: 

2019 
Date of publication: 

06.09.2019 