Ordered Level Planarity, Geodesic Planarity and Bi-Monotonicity

摘要

We introduce and study the problem ORDERED LEVEL PLANARITY which asks for a planar drawing of a graph such that vertices are placed at prescribed positions in the plane and such that every edge is realized as a y-monotone curve. This can be interpreted as a variant of LEVEL PLANARITY in which the vertices on each level appear in a prescribed total order. We establish a complexity dichotomy with respect to both the maximum degree and the level-width, that is, the maximum number of vertices that share a level. Our study of ORDERED LEVEL PLANARITY is motivated by connections to several other graph drawing problems. GEODESIC PLANARITY asks for a planar drawing of a graph such that vertices are placed at prescribed positions in the plane and such that every edge e is realized as a polygonal path p composed of line segments with two adjacent directions from a given set S of directions symmetric with respect to the origin. Our results on ORDERED LEVEL PLANARITY imply NP-hardness for any S with |S| ≥ 4 even if the given graph is a matching. Katz, Krug, Rutter and Wolff claimed that for matchings MANHATTAN GEODESIC PLANARITY, the case where S contains precisely the horizontal and vertical directions, can be solved in polynomial time [GD 2009]. Our results imply that this is incorrect unless P = NP. Our reduction extends to settle the complexity of the BI-MONOTONICITY problem, which was proposed by Fulek, Pelsmajer, Schaefer and Stefankovic. ORDERED LEVEL PLANARITY turns out to be a special case of T-LEVEL PLANARITY, CLUSTERED LEVEL PLANARITY and CONSTRAINED LEVEL PLANARITY. Thus, our results strengthen previous hardness results. In particular, our reduction to CLUSTERED LEVEL PLANARITY generates instances with only two non-trivial clusters. This answers a question posed by Angelini, Da Lozzo, Di Battista, Frati and Roselli.