Abstract
We study a prototype Crossing Minimization problem, defined as follows. Let F be an infinite family of (possibly vertexlabeled) 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 nonnegative 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 NPhardness and W[1]hardness results, and ETHbased lower bounds. Specifically, suppose that the input also contains a collection D of d noncrossing 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 nontrivial 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 twolayer drawing. For d=2, we consider three basic choices of F. For perfect matchings, we show (i) NPhardness with an ETHbased 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) NPhardness and W[1]hardness, and (ii) membership in XP.
BibTeX  Entry
@InProceedings{agrawal_et_al:LIPIcs:2019:10411,
author = {Akanksha Agrawal and Grzegorz Guspiel and Jayakrishnan Madathil and Saket Saurabh and Meirav Zehavi},
title = {{Connecting the Dots (with Minimum Crossings)}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {7:17:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771047},
ISSN = {18688969},
year = {2019},
volume = {129},
editor = {Gill Barequet and Yusu Wang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10411},
URN = {urn:nbn:de:0030drops104117},
doi = {10.4230/LIPIcs.SoCG.2019.7},
annote = {Keywords: crossing minimization, parameterized complexity, FPT algorithm, polynomial kernel, W[1]hardness}
}
Keywords: 

crossing minimization, parameterized complexity, FPT algorithm, polynomial kernel, W[1]hardness 
Seminar: 

35th International Symposium on Computational Geometry (SoCG 2019) 
Issue Date: 

2019 
Date of publication: 

17.06.2019 