Geometric Crossing-Minimization - A Scalable Randomized Approach

Authors Marcel Radermacher, Ignaz Rutter



PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.76.pdf
  • Filesize: 0.69 MB
  • 16 pages

Document Identifiers

Author Details

Marcel Radermacher
  • Department of Computer Science, Karlsruhe Institute of Technology, Germany
Ignaz Rutter
  • Department of Computer Science and Mathematics, University of Passau, Germany

Cite AsGet BibTex

Marcel Radermacher and Ignaz Rutter. Geometric Crossing-Minimization - A Scalable Randomized Approach. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 76:1-76:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ESA.2019.76

Abstract

We consider the minimization of edge-crossings 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 NP-hard [Daniel Bienstock, 1991]. Crossing-minimization, 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 crossing-minimization in geometric graphs with less than 200 edges. The described heuristics base on the primitive operation of moving a single vertex v to its crossing-minimal 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 speed-up 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 crossing-minimal 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 co-crossing number of a degree-k 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 degree-distribution different strategies result in the fewest number of crossings.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Mathematics of computing → Graph algorithms
Keywords
  • Geometric Crossing Minimization
  • Randomization
  • Approximation
  • VC-Dimension
  • Experiments

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Oswin Aichholzer. On the Rectilinear Crossing Number. (http://www.ist.tugraz.at/staff/aichholzer/research/rp/triangulations/crossing), May 2017.
  2. David A. Bader, Andrea Kappes, Henning Meyerhenke, Peter Sanders, Christian Schulz, and Dorothea Wagner. Benchmarking for Graph Clustering and Partitioning. In Encyclopedia of Social Network Analysis and Mining, 2nd Edition. Springer-Verlag, 2018. URL: https://doi.org/10.1007/978-1-4939-7131-2_23.
  3. Michael A. Bekos, Henry Förster, Christian Geckeler, Lukas Holländer, Michael Kaufmann, Amadäus M. Spallek, and Jan Splett. A Heuristic Approach Towards Drawings of Graphs with High Crossing Resolution. In Proceedings of the 26th International Symposium on Graph Drawing (GD'18), volume 11282 of Lecture Notes in Computer Science, pages 271-285, 2018. URL: https://doi.org/10.1007/978-3-030-04414-5_19.
  4. John L. Bentley and Thomas A. Ottmann. Algorithms for Reporting and Counting Geometric Intersections. IEEE Transactions on Computers, C-28(9):643-647, 1979. Google Scholar
  5. Daniel Bienstock. Some Provably Hard Crossing Number Problems. Discrete & Computational Geometry, 6(1):443-459, 1991. URL: https://doi.org/10.1007/BF02574701.
  6. Christoph Buchheim, Markus Chimani, Carsten Gutwenger, Michael Jünger, and Petra Mutzel. Crossings and Planarization. In Roberto Tamassia, editor, Handbook of Graph Drawing and Visualization, chapter 2, pages 43-85. Chapman and Hall/CRC, 2013. Google Scholar
  7. Markus Chimani, Carsten Gutwenger, Michael Jünger, Gunnar W. Klau, Karsten Klein, and Petra Mutzel. The Open Graph Drawing Framework (OGDF). In Roberto Tamassia, editor, Handbook of Graph Drawing and Visualization, chapter 17, pages 543-569. Chapman and Hall/CRC, 2013. Google Scholar
  8. Markus Chimani and Petr Hlinený. Inserting Multiple Edges into a Planar Graph. In Sándor Fekete and Anna Lubiw, editors, Proceedings of the 32nd Annual Symposium on Computational Geometry (SoCG'16), volume 51 of Leibniz International Proceedings in Informatics (LIPIcs), pages 30:1-30:15. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.SoCG.2016.30.
  9. Timothy A. Davis and Yifan Hu. The University of Florida Sparse Matrix Collection. ACM Transactions on Mathematical Software, 38(1):1:1-1:25, 2011. URL: https://doi.org/10.1145/2049662.2049663.
  10. Almut Demel, Dominik Dürrschnabel, Tamara Mchedlidze, Marcel Radermacher, and Lasse Wulf. A Greedy Heuristic for Crossing-Angle Maximization. In Proceedings of the 26th International Symposium on Graph Drawing (GD'18), Lecture Notes in Computer Science, pages 286-299, 2018. URL: https://doi.org/10.1007/978-3-030-04414-5_20.
  11. Ruy Fabila-Monroy and Jorge López. Computational Search of Small Point Sets with Small Rectilinear Crossing Number. Journal of Graph Algorithms and Applications, 18(3):393-399, 2014. URL: https://doi.org/10.7155/jgaa.00328.
  12. Emden R. Gansner, Yehuda Koren, and Stephen North. Graph Drawing by Stress Majorization. In János Pach, editor, Proceedings of the 12th International Symposium on Graph Drawing (GD'04), volume 3383 of Lecture Notes in Computer Science, pages 239-250. Springer Berlin/Heidelberg, 2005. URL: https://doi.org/10.1007/978-3-540-31843-9_25.
  13. Michael R. Garey and David S. Johnson. Crossing Number is NP-Complete. SIAM Journal on Algebraic and Discrete Methods, 4(3):312-316, 1983. Google Scholar
  14. Carsten Gutwenger, Petra Mutzel, and René Weiskircher. Inserting an Edge into a Planar Graph. Algorithmica, 41(4):289-308, 2005. URL: https://doi.org/10.1007/s00453-004-1128-8.
  15. Sariel Har-Peled and Micha Sharir. Relative (p,ε)-Approximations in Geometry. Discrete & Computational Geometry, 45(3):462-496, 2011. URL: https://doi.org/10.1007/s00454-010-9248-1.
  16. Stephen G. Kobourov. Force-Directed Drawing Algorithms. In Roberto Tamassia, editor, Handbook of Graph Drawing and Visualization, chapter 12. Chapman and Hall/CRC, 2013. Google Scholar
  17. Yi Li, Philip M. Long, and Aravind Srinivasan. Improved Bounds on the Sample Complexity of Learning. Journal of Computer and System Sciences, 62(3):516-527, 2001. URL: https://doi.org/10.1006/jcss.2000.1741.
  18. Jiří Matoušek. Lectures on Discrete Geometry, volume 212. Springer New York, 2002. Google Scholar
  19. Henning Meyerhenke, Martin Nöllenburg, and Christian Schulz. Drawing Large Graphs by Multilevel Maxent-Stress Optimization. IEEE Transactions on Visualization and Computer Graphics, 24(5):1814-1827, 2018. URL: https://doi.org/10.1109/TVCG.2017.2689016.
  20. Thomas L. Moore. Using Euler’s Formula to Solve Plane Separation Problems. The College Mathematics Journal, 22(2):125-130, 1991. Google Scholar
  21. Marcel Radermacher, Klara Reichard, Ignaz Rutter, and Dorothea Wagner. A Geometric Heuristic for Rectilinear Crossing Minimization. In Proceedings of the 20th Workshop on Algorithm Engineering and Experiments (ALENEX'18), pages 129-138, 2018. URL: https://doi.org/10.1137/1.9781611975055.12.
  22. David J. Sheskin. Handbook of Parametric and Nonparametric Statistical Procedures. Chapman and Hall/CRC, 2003. Google Scholar
  23. Angelika Steger and Nicholas C. Wormald. Generating Random Regular Graphs Quickly. Combinatorics, Probability and Computing, 8(4):377–396, 1999. Google Scholar
  24. The CGAL Project. CGAL User and Reference Manual (http://doc.cgal.org/4.10/Manual/packages.html). CGAL Editorial Board, 4.10 edition, 2017.
  25. Vladimir N. Vapnik and Alexey Y. Chervonenkis. On the Uniform Convergence of Relative Frequencies of Event to their Probabilities. Theory of Probability & Its Application, 16(2):264-280, 1971. Google Scholar
  26. Imrich Vrt'o. Bibliography on Crossing Numbers of Graphs. (ftp://ftp.ifi.savba.sk/pub/imrich/crobib.pdf), 2014.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail