Aligned Drawings of Planar Graphs

Abstract

Let $G$ be a graph that is topologically embedded in the plane and let $\mathcal{A}$ be an arrangement of pseudolines intersecting the drawing of $G$. An aligned drawing of $G$ and $\mathcal{A}$ is a planar polyline drawing $\hat{I}“$ of $G$ with an arrangement $A$ of lines so that $\hat{I}“$ and $A$ are homeomorphic to $G$ and $\mathcal{A}$. We show that if $\mathcal{A}$ is stretchable and every edge $e$ either entirely lies on a pseudoline or it has at most one intersection with $\mathcal{A}$, then $G$ and $\mathcal{A}$ have a straight-line aligned drawing. In order to prove this result, we strengthen a result of Da Lozzo et al., and prove that a planar graph $G$ and a single pseudoline $\mathcal{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.

Preliminary work appeared in the Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)