Ordered Level Planarity, Geodesic Planarity and BiMonotonicityKlemz, Boris and Rote, Günter (2017) Ordered Level Planarity, Geodesic Planarity and BiMonotonicity. In: Graph Drawing and Network Visualization. GD 2017, September 2527 , pp. 440454(Official URL: https://doi.org/10.1007/9783319739151_34). Full text not available from this repository.
Official URL: https://doi.org/10.1007/9783319739151_34
AbstractWe 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 ymonotone 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 levelwidth, 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 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 . Our reduction extends to settle the complexity of the BiMonotonicity problem, which was proposed by Fulek, Pelsmajer, Schaefer and Štefankovič. Ordered Level Planarity turns out to be a special case of TLevel 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 nontrivial clusters. This answers a question posed by Angelini, Da Lozzo, Di Battista, Frati and Roselli.
Actions (login required)
