Aligned Drawings of Planar Graphs - Mchedlidze, Tamara; Radermacher, Marcel; Rutter, Ignaz (Journal of Graph Algorithms and Applications, 2018)
Let G be a graph that is topologically embedded in the plane and let A be an arrangement of pseudolines intersecting the drawing of G. An aligned drawing of G and A is a planar polyline drawing Γ of G with an arrangement A of lines so that Γ and A are homeomorphic to G and A. We show that if A is stretchable and every edge e either entirely lies on a pseudoline or it has at most one intersection with A, then G and A have a straight-line aligned drawing. In order to prove this result, we strengthen a result of Da Lozzo et al. [Da Lozzo et al. GD 2016], and prove that a planar graph G and a single pseudoline L have an aligned drawing with a prescribed convex drawing of the outer face. We also study the less restrictive version of the alignment problem with respect to one line, where only a set of vertices is given and we need to determine whether they can be collinear. We show that the problem is NP-complete but fixed-parameter tractable.