Minimizing the crossing number of a graph, i.e., the minimum number of pairwise edge crossings over all drawings in the plane, is a notoriously computationally hard problem. It remains hard even under very restrictive settings of the input. We survey some the many know hardness results in this area, and, in response to a long standing open question of the area, we present a new hardness reduction proving that the crossing number problem remains NP-complete for graphs of constant tree-width and path-width.
[+]Consider a graph drawn on a surface (for example, the plane minus a finite set of obstacle points), possibly with crossings. We provide a polynomial time algorithm to decide whether such a drawing can be untangled, namely, if one can slide the vertices and edges of the graph on the surface (avoiding the obstacles) to remove all crossings; in other words, whether the drawing is homotopic to an embedding. While the problem boils down to planarity testing when the surface is the sphere or the disk (or equivalently the plane without any obstacle), the other cases have never been studied before, except when the input graph is a cycle, in an abundant literature in topology and more recently by Despré and Lazarus.
[+]CONGEST is a model in which computers distributed over a network graph have to efficiently exchange quantified information in order to solve a problem. One of its most natural problems is the detection of subgraphs in the network. In this talk will be given an overview of the problem of cycle detection in the CONGEST model and especially of our latest state-of-the-art algorithm for even-length cycles. If the time allows, the quantum approach to quadratically speed up the detection will also be addressed.
[+]