Document Open Access Logo

Connecting the Dots (with Minimum Crossings)

Authors Akanksha Agrawal, Grzegorz Guśpiel, Jayakrishnan Madathil, Saket Saurabh, Meirav Zehavi

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2019.7.pdf
  • Filesize: 2.14 MB
  • 17 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • crossing minimization
  • parameterized complexity
  • FPT algorithm
  • polynomial kernel
  • W[1]-hardness

Metrics

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

Abstract

We study a prototype Crossing Minimization problem, defined as follows. Let F be an infinite family of (possibly vertex-labeled) graphs. Then, given a set P of (possibly labeled) n points in the Euclidean plane, a collection L subseteq Lines(P)={l: l is a line segment with both endpoints in P}, and a non-negative integer k, decide if there is a subcollection L'subseteq L such that the graph G=(P,L') is isomorphic to a graph in F and L' has at most k crossings. By G=(P,L'), we refer to the graph on vertex set P, where two vertices are adjacent if and only if there is a line segment that connects them in L'. Intuitively, in Crossing Minimization, we have a set of locations of interest, and we want to build/draw/exhibit connections between them (where L indicates where it is feasible to have these connections) so that we obtain a structure in F. Natural choices for F are the collections of perfect matchings, Hamiltonian paths, and graphs that contain an (s,t)-path (a path whose endpoints are labeled). While the objective of seeking a solution with few crossings is of interest from a theoretical point of view, it is also well motivated by a wide range of practical considerations. For example, links/roads (such as highways) may be cheaper to build and faster to traverse, and signals/moving objects would collide/interrupt each other less often. Further, graphs with fewer crossings are preferred for graphic user interfaces.
As a starting point for a systematic study, we consider a special case of Crossing Minimization. Already for this case, we obtain NP-hardness and W[1]-hardness results, and ETH-based lower bounds. Specifically, suppose that the input also contains a collection D of d non-crossing line segments such that each point in P belongs to exactly one line in D, and L does not contain line segments between points on the same line in D. Clearly, Crossing Minimization is the case where d=n - then, P is in general position. The case of d=2 is of interest not only because it is the most restricted non-trivial case, but also since it corresponds to a class of graphs that has been well studied - specifically, it is Crossing Minimization where G=(P,L) is a (bipartite) graph with a so called two-layer drawing. For d=2, we consider three basic choices of F. For perfect matchings, we show (i) NP-hardness with an ETH-based lower bound, (ii) solvability in subexponential parameterized time, and (iii) existence of an O(k^2)-vertex kernel. Second, for Hamiltonian paths, we show (i) solvability in subexponential parameterized time, and (ii) existence of an O(k^2)-vertex kernel. Lastly, for graphs that contain an (s,t)-path, we show (i) NP-hardness and W[1]-hardness, and (ii) membership in XP.

Cite As Get BibTex

Akanksha Agrawal, Grzegorz Guśpiel, Jayakrishnan Madathil, Saket Saurabh, and Meirav Zehavi. Connecting the Dots (with Minimum Crossings). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.SoCG.2019.7

Author Details

Akanksha Agrawal
  • Ben-Gurion University, Beer-Sheva, Israel
Grzegorz Guśpiel
  • Theoretical Computer Science Department, Faculty of Mathematics and Computer Science, Jagiellonian University, {Krak\texorpdfstringó{o}w, Poland}
Jayakrishnan Madathil
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
Saket Saurabh
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
  • University of Bergen, Bergen, Norway
Meirav Zehavi
  • Ben-Gurion University, Beer-Sheva, Israel

Funding

  • Agrawal, Akanksha: The work was carried out when the author was employed at Hungarian Academy of Sciences, and was supported by ERC Consolidator Grant SYSTEMATICGRAPH (No. 46 725978).
  • Guśpiel, Grzegorz: Partially supported by the MNiSW grant DI2013 000443.
  • Saurabh, Saket: Supported by ERC Consolidator Grant LOPPRE (No. 819416).
  • Zehavi, Meirav: Supported by ISF grant no. 1176/18.

Acknowledgements

We thank Grzegorz Gutowski and Paweł Rzążewski for many valuable comments regarding the NP-hardness proof for CM-PM.

References

  1. A. Karim Abu-Affash, Ahmad Biniaz, Paz Carmi, Anil Maheshwari, and Michiel H. M. Smid. Approximating the bottleneck plane perfect matching of a point set. Comput. Geom., 48(9):718-731, 2015. Google Scholar
  2. A. Karim Abu-Affash, Paz Carmi, Matthew J. Katz, and Yohai Trabelsi. Bottleneck non-crossing matching in the plane. Comput. Geom., 47(3):447-457, 2014. Google Scholar
  3. Jihad Al-Oudatallah, Fariz Abboud, Mazen Khoury, and Hassan Ibrahim. Overlapping Signal Separation Method Using Superresolution Technique Based on Experimental Echo Shape. Advances in Acoustics and Vibration, pages 1-9, 2017. Google Scholar
  4. Victor Alvarez, Karl Bringmann, Radu Curticapean, and Saurabh Ray. Counting crossing-free structures. In Symposuim on Computational Geometry 2012, SoCG '12, Chapel Hill, NC, USA, June 17-20, 2012, pages 61-68, 2012. Google Scholar
  5. Marc Benkert, Herman J. Haverkort, Moritz Kroll, and Martin Nöllenburg. Algorithms for Multi-criteria One-Sided Boundary Labeling. In Graph Drawing, 15th International Symposium, GD 2007, Sydney, Australia, September 24-26, 2007. Revised Papers, pages 243-254, 2007. Google Scholar
  6. Therese C. Biedl, Franz-Josef Brandenburg, and Xiaotie Deng. Crossings and Permutations. In Proceeding of the 13th International Symposium on Graph Drawing, GD, volume 3843 of Lecture Notes in Computer Science, pages 1-12. Springer, 2005. Google Scholar
  7. Édouard Bonnet, Tillmann Miltzow, and Paweł Rzążewski. Complexity of Token Swapping and Its Variants. Algorithmica, October 2017. Google Scholar
  8. Sergio Cabello and Bojan Mohar. Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard. SIAM J. Comput., 42(5):1803-1829, 2013. Google Scholar
  9. John Gunnar Carlsson, Benjamin Armbruster, Saladi Rahul, and Haritha Bellam. A Bottleneck Matching Problem with Edge-Crossing Constraints. Int. J. Comput. Geometry Appl., 25(4):245-262, 2015. Google Scholar
  10. Xuanwu Chen and Ming S. Lee. A case study on multi-lane roundabouts under congestion: Comparing software capacity and delay estimates with field data. Journal of Traffic and Transportation Engineering (English Edition), 3(2):154-165, 2016. Google Scholar
  11. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. Google Scholar
  12. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  13. Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G Tollis. Algorithms for drawing graphs: an annotated bibliography. Computational Geometry, 4(5):235-282, 1994. Google Scholar
  14. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  15. Vida Dujmovic, Michael R. Fellows, Michael T. Hallett, Matthew Kitching, Giuseppe Liotta, Catherine McCartin, Naomi Nishimura, Prabhakar Ragde, Frances A. Rosamond, Matthew Suderman, Sue Whitesides, and David R. Wood. On the Parameterized Complexity of Layered Graph Drawing. In 9th Annual European Symposium on Algorithms, ESA 2001, Proceedings, pages 488-499, 2001. Google Scholar
  16. Peter Eades and Sue Whitesides. Drawing graphs in two layers. Theoretical Computer Science, 131(2):361-374, 1994. Google Scholar
  17. Peter Eades and Nicholas C. Wormald. Edge crossings in drawings of bipartite graphs. Algorithmica, 11(4):379-403, 1994. Google Scholar
  18. Jack Edmonds. Paths, Trees and Flowers. Canadian Journal of Mathematics, pages 449-467, 1965. Google Scholar
  19. Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, and Stéphane Vialette. On the parameterized complexity of multiple-interval graph problems. Theoretical computer science, 410(1):53-61, 2009. Google Scholar
  20. Fedor V Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: theory of parameterized preprocessing. Cambridge University Press, 2019. Google Scholar
  21. Per Garder. Pedestrian safety at traffic signals: A study carried out with the help of a traffic conflicts technique. Accident Analysis &Prevention, 21(5):435-444, 1989. Google Scholar
  22. M R Garey and D S Johnson. Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman, New York, 1979. Google Scholar
  23. Michael R Garey and David S Johnson. Crossing number is NP-complete. SIAM Journal on Algebraic Discrete Methods, 4(3):312-316, 1983. Google Scholar
  24. Martin Grohe. Computing crossing numbers in quadratic time. In Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 231-236, 2001. Google Scholar
  25. Magnús M. Halldórsson, Christian Knauer, Andreas Spillner, and Takeshi Tokuyama. Fixed-Parameter Tractability for Non-Crossing Spanning Trees. In Algorithms and Data Structures, 10th International Workshop, WADS 2007, Halifax, Canada, August 15-17, 2007, Proceedings, pages 410-421, 2007. Google Scholar
  26. Godfrey H Hardy and Srinivasa Ramanujan. Asymptotic formulaæ in combinatory analysis. Proceedings of the London Mathematical Society, 2(1):75-115, 1918. Google Scholar
  27. Petr Hlinený. Crossing number is hard for cubic graphs. J. Comb. Theory, Ser. B, 96(4):455-471, 2006. Google Scholar
  28. Petr Hlinený and Marek Dernár. Crossing Number is Hard for Kernelization. In 32nd International Symposium on Computational Geometry, SoCG 2016, June 14-18, 2016, Boston, MA, USA, pages 42:1-42:10, 2016. Google Scholar
  29. John E. Hopcroft and Robert Endre Tarjan. Efficient Algorithms for Graph Manipulation [H] (Algorithm 447). Commun. ACM, 16(6):372-378, 1973. Google Scholar
  30. Klaus Jansen and Gerhard J. Woeginger. The Complexity of Detecting Crossingfree Configurations in the Plane. BIT, 33(4):580-595, 1993. Google Scholar
  31. Michael Junger and Petra Mutzel. Graph Drawing Software. Springer-Verlag, Berlin, Heidelberg, 2003. Google Scholar
  32. Ken-ichi Kawarabayashi and Bruce A. Reed. Computing crossing number in linear time. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 382-390, 2007. Google Scholar
  33. Fabian Klute and Martin Nöllenburg. Minimizing Crossings in Constrained Two-Sided Circular Graph Layouts. In 34th International Symposium on Computational Geometry, SoCG 2018, June 11-14, 2018, Budapest, Hungary, pages 53:1-53:14, 2018. Google Scholar
  34. Jan Kratochvíl, Anna Lubiw, and Jaroslav Nešetřil. Noncrossing Subgraphs in Topological Layouts. SIAM J. Discret. Math., 4(2):223-244, March 1991. Google Scholar
  35. Mukkai S Krishnamoorthy and Narsingh Deo. Node-deletion NP-complete problems. SIAM Journal on Computing, 8(4):619-625, 1979. Google Scholar
  36. Martin I Krzywinski, Jacqueline E Schein, Inanc Birol, Joseph Connors, Randy Gascoyne, Doug Horsman, Steven J Jones, and Marco A Marra. Circos: An information aesthetic for comparative genomics. Genome Research, 19(9):1639-1645, 2009. Google Scholar
  37. J. Malik, J. Weber, Q. T. Luong, and D. Roller. Smart cars and smart roads. In Proceedings 6th. British Machine Vision Conference, pages 367-381, 1995. Google Scholar
  38. Dániel Marx and Tillmann Miltzow. Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems. In 32nd International Symposium on Computational Geometry, SoCG 2016, June 14-18, 2016, Boston, MA, USA, pages 52:1-52:16, 2016. Google Scholar
  39. Tillmann Miltzow. Subset token swapping on a path and bipartite minimum crossing matchings. In Order and Geometry Workshop, Problem booklet., pages 5-6, 2016. URL: http://orderandgeometry2016.tcs.uj.edu.pl/docs/OG2016-ProblemBooklet.pdf.
  40. Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, and Takeaki Uno. Approximation and Hardness of Token Swapping. In 24th Annual European Symposium on Algorithms, ESA 2016, pages 66:1-66:15, 2016. Google Scholar
  41. Monroe M. Newborn and William O. J. Moser. Optimal crossing-free Hamiltonian circuit drawings of K_n. J. Comb. Theory, Ser. B, 29(1):13-26, 1980. Google Scholar
  42. Michael Osigbemeh, Michael Onuu, and Olumuyiwa Asaolu. Design and development of an improved traffic light control system using hybrid lighting system. Journal of Traffic and Transportation Engineering (English Edition), 4(1):88-95, 2017. Special Issue: Driver Behavior, Highway Capacity and Transportation Resilience. Google Scholar
  43. Marcus Schaefer. The Graph Crossing Number and its Variants: A Survey. The Electronic Journal of Combinatorics, 20, April 2013. Google Scholar
  44. Carl Sechen. VLSI placement and global routing using simulated annealing, volume 54. Springer Science &Business Media, 2012. Google Scholar
  45. Micha Sharir and Emo Welzl. On the Number of Crossing-Free Matchings, Cycles, and Partitions. SIAM J. Comput., 36(3):695-720, 2006. Google Scholar
  46. Paul Turán. A note of welcome. Journal of Graph Theory, 1(1):7-9, 1997. Google Scholar
  47. Manuel Wettstein. Counting and enumerating crossing-free geometric graphs. JoCG, 8(1):47-77, 2017. Google Scholar
  48. Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno. Swapping Labeled Tokens on Graphs. In Alfredo Ferro, Fabrizio Luccio, and Peter Widmayer, editors, Fun with Algorithms, pages 364-375, 2014. Google Scholar
  49. Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno. Swapping labeled tokens on graphs. Theoretical Computer Science, 586:81-94, 2015. Fun with Algorithms. Google Scholar
  50. Lanbo Zheng and Christoph Buchheim. A New Exact Algorithm for the Two-Sided Crossing Minimization Problem. In Proceedings of the First International Conference on Combinatorial Optimization and Applications, COCOA, volume 4616 of Lecture Notes in Computer Science, pages 301-310. Springer, 2007. Google Scholar
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
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact