AI summaryⓘ
The authors study the problem of placing graph vertices onto specific allowed points to draw the graph without edges crossing, a generalization of the Point Set Embeddability problem. They find this problem is hard (NP-hard) even for simple graphs like matchings when points form a convex shape and vertices have at most two allowed positions. They also develop efficient algorithms for connected graphs under certain conditions, partially solving an open question. For more general point sets, the problem remains hard even for simple paths, but they present some fixed-parameter tractable (FPT) algorithms based on vertex cover size, and explore how labeling complexity affects difficulty. Finally, the authors analyze related optimization tasks, proving some are hard and others fall into clear complexity categories depending on parameters.
Point Set EmbeddabilityPlanar Straight-Line DrawingNP-hardnessFixed-Parameter Tractable (FPT)Combinatorial EmbeddingVertex CoverParameterized ComplexityGraph MatchingConvex PositionAPX-hardness
Authors
Thomas Depian, Joseph Dorfer, Boris Klemz, Matthias Pfretzschner, Lena Schlipf
Abstract
Deciding whether a given graph admits a planar straight-line drawing where each vertex is placed on some point from a given finite point set is known as Point Set Embeddability and is a classical problem in graph drawing. In this paper, we study the more general embeddability question where the placement of each vertex $v$ is restricted to a list $L(v)$ of admissible points. We first study the case where the given point set is in convex position. We show that this case is NP-hard even if the given graph is a matching and bi-labeled, i.e., each vertex has at most 2 admissible points. On the positive side, we present two efficient algorithms for the case where the given graph $G$ is connected (and not necessarily bi-labeled): if $G$ is equipped with a combinatorial embedding that needs to be respected, we can solve the problem in polynomial time; otherwise we can solve it in FPT-time with regard to the maximum vertex degree. In particular, this answers an open question by Frati, Glisse, Lenhart, Liotta, Mchedlidze, and Nishat [GD'13]. We then turn our attention to the more general case where the given point set is not necessarily in convex position. Here, we show NP-hardness for bi-labeled paths; notably these graphs have a unique combinatorial embedding and maximum degree two. We also present an FPT-algorithm with respect to the vertex cover number for the special case of bi-labeled graphs. We complement this latter result by establishing paraNP-hardness in the tri-labeled setting for vertex cover number 2 and polynomial-time solvability for vertex cover number 1 and arbitrary $L$. Finally, we study optimization and extension variants, where we want to maximize the number of edges or extend a partial drawing, respectively. For the former, we show APX-hardness and for the latter, we provide a parameterized complexity dichotomy under natural extension parameters.