Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLink Crossing Number is NP-hard
152
0
0.0
(
0
)
Added by
Arnaud de Mesmay
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We show that determining the crossing number of a link is NP-hard. For some weaker notions of link equivalence, we also show NP-completeness.
rate research
Read More
In this paper, we show that deciding rigid foldability of a given crease pattern using all creases is weakly NP-hard by a reduction from Partition, and that deciding rigid foldability with optional creases is strongly NP-hard by a reduction from 1-in-3 SAT. Unlike flat foldability of origami or flexibility of other kinematic linkages, whose complexity originates in the complexity of the layer ordering and possible self-intersection of the material, rigid foldability from a planar state is hard even though there is no potential self-intersection. In fact, the complexity comes from the combinatorial behavior of the different possible rigid folding configurations at each vertex. The results underpin the fact that it is harder to fold from an unfolded sheet of paper than to unfold a folded state back to a plane, frequently encountered problem when realizing folding-based systems such as self-folding matter and reconfigurable robots.
In a geometric network G = (S, E), the graph distance between two vertices u, v in S is the length of the shortest path in G connecting u to v. The dilation of G is the maximum factor by which the graph distance of a pair of vertices differs from their Euclidean distance. We show that given a set S of n points with integer coordinates in the plane and a rational dilation delta > 1, it is NP-hard to determine whether a spanning tree of S with dilation at most delta exists.
Weak unit disk contact graphs are graphs that admit a representation of the nodes as a collection of internally disjoint unit disks whose boundaries touch if there is an edge between the corresponding nodes. We provide a gadget-based reduction to show that recognizing embedded caterpillars that admit a weak unit disk contact representation is NP-hard.
Research about crossings is typically about minimization. In this paper, we consider emph{maximizing} the number of crossings over all possible ways to draw a given graph in the plane. Alpert et al. [Electron. J. Combin., 2009] conjectured that any graph has a emph{convex} straight-line drawing, e.g., a drawing with vertices in convex position, that maximizes the number of edge crossings. We disprove this conjecture by constructing a planar graph on twelve vertices that allows a non-convex drawing with more crossings than any convex one. Bald et al. [Proc. COCOON, 2016] showed that it is NP-hard to compute the maximum number of crossings of a geometric graph and that the weighted geometric case is NP-hard to approximate. We strengthen these results by showing hardness of approximation even for the unweighted geometric case and prove that the unweighted topological case is NP-hard.
176 -
Adrien Friggeri
, Eric Fleury (ENS / LIPn Laboratoire de lInformatique du Parallelisme / INRIA Grenoblen Rh^one-Alpes
2011
We show that the problem of finding a set with maximum cohesion in an undirected network is NP-hard.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
