1 Introduction
In this paper we introduce Ordered Level Planarity and study its complexity. We establish connections to several other graph drawing problems, which we survey in this first section. We proceed from general problems to more and more constrained ones.
Upward Planarity: An upward planar drawing of a directed graph is a plane drawing where every edge is realized as a monotone curve that goes upward from to . Such drawings provide a natural way of visualizing a partial order on a set of items. The problem Upward Planarity of testing whether a directed graph has an upward planar drawing is complete [12]. However, if the coordinate of each vertex is prescribed, the problem can be solved in polynomial time [19]. This is captured by the notion of level graphs.
Level Planarity: A level graph is a directed graph together with a level assignment where is a surjective map with for every edge . Value is the height of . The vertex set is called the th level of and is its width. The levelwidth of is the maximum width of any level in . A level planar drawing of is an upward planar drawing of where the coordinate of each vertex is . The horizontal line with coordinate is denoted by . The problem Level Planarity asks whether a given level graph has a level planar drawing. The study of the complexity of Level Planarity has a long history [9, 17, 18, 19, 11], culminating in a lineartime approach [19]. Level Planarity has been extended to drawings of level graphs on surfaces different from the plane such as standing cylinder, a rolling cylinder or a torus [1, 4, 5].
An important special case are proper level graphs, that is, level graphs in which for every edge . Instances of Level Planarity can be assumed to be proper without loss of generality by subdividing long edges [19, 9]. However, in variations of Level Planarity where we impose additional constraints, the assumption that instances are proper can have a strong impact on the complexity of the respective problems [2].
Level Planarity with Various Constraints: Clustered Level Planarity is a combination of Cluster Planarity and Level Planarity. The task is to find a level planar drawing while simultaneously visualizing a given cluster hierarchy according to the rules of Cluster Planarity. The problem is complete in general [2], but efficiently solvable for proper instances [10, 2].
TLevel Planarity is a consecutivityconstrained version of Level Planarity: every level is equipped with a tree whose set of leaves is . For every inner node of the leaves of the subtree rooted at have to appear consecutively along . The problem is complete in general [2], but efficiently solvable for proper instances [21, 2]. The precise definitions and a longer discussion about the related work are deferred to Appendix 0.C.
Very recently, Brückner and Rutter [7] explored a variant of Level Planarity in which the lefttoright order of the vertices on each level has to be a linear extension of a given partial order. They refer to this problem as Constrained Level Planarity and they provide an efficient algorithm for singlesource graphs and show completeness of the general case.
A Common Special Case  Ordered Level Planarity: We introduce a natural variant of Level Planarity that specifies a total order for the vertices on each level. An ordered level graph is a triple where is a level graph and is a level ordering for . We require that restricted to domain bijectively maps to . An ordered level planar drawing of an ordered level graph is a level planar drawing of where for every the coordinate of is . Thus, the position of every vertex is fixed. The problem Ordered Level Planarity asks whether a given ordered level graph has an ordered level planar drawing.
In the above definitions, the  and coordinates assigned via and merely act as a convenient way to encode total and partial orders respectively. In terms of realizability, the problems are equivalent to generalized versions where and map to the reals. In other words, the fixed vertex positions can be any points in the plane. All reductions and algorithms in this paper carry over to these generalized versions, if we pay the cost for presorting the vertices according to their coordinates. Ordered Level Planarity is also equivalent to a relaxed version where we only require that the vertices of each level appear along according to the given total order without insisting on specific coordinates. We make use of this equivalence in many of our figures for the sake of visual clarity.
Geodesic Planarity: Let be a finite set of directions symmetric with respect to the origin, i.e. for each direction , the reverse direction is also contained in . A plane drawing of a graph is geodesic with respect to if every edge is realized as a polygonal path composed of line segments with two adjacent directions from . Two directions of are adjacent if they appear consecutively in the projection of to the unit circle. Such a path is a geodesic with respect to some polygonal norm that corresponds to . An instance of the decision problem Geodesic Planarity is a 4tuple where is a graph, and map from to the reals and is a set of directions as stated above. The task is to decide whether has a geodesic drawing, that is, has a geodesic drawing with respect to in which every vertex is placed at .
Katz, Krug, Rutter and Wolff [20] study Manhattan Geodesic Planarity, which is the special case of Geodesic Planarity where the set consists of the two horizontal and the two vertical directions. Geodesic drawings with respect to this set of direction are also referred to as orthogeodesic drawings [14, 13]. Katz et al. [20] show that a variant of Manhattan Geodesic Planarity in which the drawings are restricted to the integer grid is hard even if is a perfect matching. The proof is by reduction from 3Partition and makes use of the fact the number of edges that can pass between two vertices on a grid line is bounded. In contrast, they claim that the standard version of Manhattan Geodesic Planarity is polynomialtime solvable for perfect matchings [20, Theorem 5]. To this end, they sketch a plane sweep algorithm that maintains a linear order among the edges that cross the sweep line. When a new edge is encountered it is inserted as low as possible subject to the constraints implied by the prescribed vertex positions. When we asked the authors for more details, they informed us that they are no longer convinced of the correctness of their approach. Theorem 1.2 of our paper implies that the approach is indeed incorrect unless .
BiMonotonicity: Fulek, Pelsmajer, Schaefer and Štefankovič [11] present a HananiTutte theorem for ymonotone drawings, that is, upward drawings in which all vertices have distinct coordinates. They accompany their result with a simple and efficient algorithm for YMonotonicity, which is equivalent to Level Planarity restricted to instances with levelwidth . They propose the problem BiMonotonicity and leave its complexity as an open problem. The input of BiMonotonicity is a triple where is a graph and and injectively map from to the reals. The task is to decide whether has a bimonotone drawing, that is, a plane drawing in which edges are realized as curves that are both monotone and monotone and in which every vertex is placed at .
Main results: In Section 3 we study the complexity of Ordered Level Planarity. While Upward Planarity is complete [12] in general but becomes polynomialtime solvable [19] for prescribed coordinates, we show that prescribing both coordinates and coordinates renders the problem complete. We complement our result with efficient approaches for some special cases of ordered level graphs and, thereby, establish a complexity dichotomy with respect to the levelwidth and the maximum degree.
Theorem 1.1
Ordered Level Planarity is complete, even for maximum degree and levelwidth . For levelwidth or or proper instances Ordered Level Planarity can be solved in linear time, where and are the maximum indegree and outdegree respectively.
Ordered Level Planarity restricted to instances with and is an elementary problem. We expect that it may serve as a suitable basis for future reductions. As a proof of concept, the remainder of this paper is devoted to establishing connections between Ordered Level Planarity and several other graph drawing problems. Theorem 1.1 serves as our key tool for settling their complexity. In Section 2 we study Geodesic Planarity and obtain:
Theorem 1.2
Geodesic Planarity is hard for any set of directions with even for perfect matchings in general position.
Observe the aforementioned discrepancy between Theorem 1.2 and the claim by Katz et al. [20] that Manhattan Geodesic Planarity for perfect matchings is in . BiMonotonicity is closely related to a special case of Manhattan Geodesic Planarity. With a simple corollary we settle the complexity of BiMonotonicity and, thus, answer the open question by Fulek et al. [11].
Theorem 1.3
BiMonotonicity is hard even for perfect matchings.
Ordered Level Planarity is an immediate and very constrained special case of Constrained Planarity. Further, in Appendix 0.C we establish Ordered Level Planarity as a special case of both Clustered Level Planarity and TLevel Planarity by providing the following reductions.
Theorem 1.4
Ordered Level Planarity with maximum degree and levelwidth reduces in linear time to TLevel Planarity with maximum degree and levelwidth .
Theorem 1.5
Ordered Level Planarity with maximum degree and levelwidth reduces in quadratic time to Clustered Level Planarity with maximum degree , levelwidth and clusters.
Angelini, Da Lozzo, Di Battista, Frati and Roselli [2] propose the complexity of Clustered Level Planarity for clustered level graphs with a flat cluster hierarchy as an open question. Theorem 1.5 answers this question by showing that hardness holds for instances with only two nontrivial clusters.
2 Geodesic Planarity and BiMonotonicity
In this section we establish that deciding whether an instance of Geodesic Planarity has a geodesic drawing is hard even if is a perfect matching and even if the coordinates assigned via and are in general position, that is, no two vertices lie on a line with a direction from . The hardness of BiMonotonicity for perfect matchings follows as a simple corollary. Our results are obtained via a reduction from Ordered Level Planarity.
Lemma 1
Let with be a finite set of directions symmetric with respect to the origin. Ordered Level Planarity with maximum degree and levelwidth reduces to Geodesic Planarity such that the resulting instances are in general position and consist of a perfect matching and direction set . The reduction can be carried out using a linear number of arithmetic operations.
Proof Sketch. In this sketch, we prove our claim only for the classical case that contains exactly the four horizontal and vertical directions. Our reduction is carried out in two steps. Let be an Ordered Level Planarity instance with maximum degree and levelwidth . In Step (i) we turn into an equivalent Geodesic Planarity instance . In Step (ii) we transform into an equivalent Geodesic Planarity instance where is a perfect matching and the vertex positions assigned via and are in general position.
Step (i): In order to transform into we apply a shearing transformation. We translate the vertices of each level by units to the right, see Figure 1(a) and Figure 1(b). Clearly, every geodesic drawing of can be turned into an ordered level planar drawing of . On the other hand, consider an ordered level planar drawing of . Without loss of generality we can assume that in all edges are realized as polygonal paths in which bend points occur only on the horizontal lines through the levels where . Further, we may assume that all bend points have coordinates in the open interval . We shear by translating the bend points and vertices of level by units to the right for , see Figure 1(b). In the resulting drawing , the vertex positions match those of . Furthermore, all edgesegments have a positive slope. Thus, since the maximum degree is we can replace all edgesegments with geodesic rectilinear paths that closely trace the segments and we obtain a geodesic drawing of , see Figure 1(c).
Step (ii): In order to turn into the equivalent instance we transform into a perfect matching. To this end, we split each vertex by replacing it with a small gadget that fits inside a square centered on the position of , see Figure 1(e). We call the square of and use , , and to denote the topright, topleft, bottomright and bottomleft corner of , respectively. We use two different sizes to ensure general position. The size of the gadget square is if and it is if . The gadget contains a degree1 vertex for every edge incident to . In the following we explain the gadget construction in detail, for an illustration see Figure 1(d). Let be an edge incident to . We create an edge where is a new vertex which is placed at if is located to the topright of and it is placed at if is located to the bottomleft of . Similarly, if is incident to a second edge , we create an edge where is placed at or depending on the position of . Finally, we create a blocking edge where is placed at and is placed at . The thereby assigned coordinates are in general position and the construction can be carried out in linear time.
Assume that has a geodesic drawing . By construction, all blocking edges have a topleft and a bottomright endpoint. On the other hand, all other edges have a bottomleft and a topright endpoint. As a result, a nonblocking edge can not pass through any gadget square , except the squares or since would have to cross the blocking edge of . Accordingly, it is straightforward to obtain a geodesic drawing of : We remove the blocking edges, reinsert the vertices of according to the mappings and and connect them to the vertices of their respective gadgets in a geodesic fashion. This can always be done without crossings. Figure 1(f) shows one possibility. If the edge from passes to the left of , we may have to choose a reflected version. Finally, we remove the vertices and which now act as subdivision vertices.
On the other hand, let be a geodesic planar drawing of . Without loss of generality, we can assume that each edge passes only through the squares of and . Furthermore, for each we can assume that its incident edges intersect the boundary of only to the topright of or to the bottomleft of , see Figure 1(g). Thus, we can simply remove the parts of the edges in the interior of the gadget squares and connect the gadget vertices to the intersection points of the edges with the gadget squares in a geodesic fashion.
The bit size of the numbers involved in the calculations of our reduction is linearly bounded in the bit size of the directions of . Together with Theorem 1.1 we obtain the proof of Theorem 1.2. The instances generated by Lemma 1 are in general position. In particular, this means that the mappings and are injective. We obtain an immediate reduction to BiMonotonicity. The correctness follows from the fact that every geodesic rectilinear path can be transformed into a bimonotone curve and vice versa. Thus, we obtain Theorem 1.3.
3 Ordered Level Planarity
To show hardness of Ordered Level Planarity we reduce from a 3Satisfiability variant described in this paragraph. A monotone 3Satisfiability formula is a Boolean 3Satisfiability formula in which each clause is either positive or negative, that is, each clause contains either exclusively positive or exclusively negative literals respectively. A planar 3SAT formula is a Boolean 3Satisfiability formula with a set of variables and a set of clauses such that its variableclause graph is planar. The graph is bipartite, i.e. every edge in is incident to both a clause vertex from and a variable vertex from . Furthermore, edge if and only if a literal of variable occurs in . Planar Monotone 3Satisfiability is a special case of 3Satisfiability where we are given a planar and monotone 3Satisfiability formula and a monotone rectilinear representation of the variableclause graph of . The representation is a contact representation on an integer grid in which the variables are represented by horizontal line segments arranged on a line . The clauses are represented by Eshapes turned by such that all positive clauses are placed above and all negative clauses are placed below , see Figure 1(a). Planar Monotone 3Satisfiability is complete [6]. We are now equipped to prove the core lemma of this section.
Lemma 2
Planar Monotone 3Satisfiability reduces in polynomial time to Ordered Level Planarity. The resulting instances have maximum degree and all vertices on levels with width at least 3 have outdegree at most and indegree at most .
Proof Sketch. We perform a polynomialtime reduction from Planar Monotone 3Satisfiability. Let be a planar and monotone 3Satisfiability formula with . Let the variableclause graph of . Let be a monotone rectilinear representation of . We construct an ordered level graph such that has an ordered level planar drawing if and only if is satisfiable. In this proof sketch we omit some technical details such as precise level assignments and level orderings.
Overview: The ordered level graph has levels which are partitioned into four tiers , , and . Each clause is associated with a clause edge starting with in tier and ending with in tier . The clause edges have to be drawn in a system of tunnels that encodes the 3Satisfiability formula . In the layout of the tunnels corresponds directly to the rectilinear representation , see Figure 1(c). For each Eshape there are three tunnels corresponding to the three literals of the associated clause. The bottom vertex of each clause edge is placed such that has to be drawn inside one of the three tunnels of the Eshape corresponding to . This corresponds to the fact that in a satisfying truth assignment every clause has at least one satisfied literal. In tier we merge all the tunnels corresponding to the same literal. We create variable gadgets that ensure that for each variable edges of clauses containing can be drawn in the tunnel associated with either the negative or the positive literal of but not both. This corresponds to the fact that every variable is set to either true or false. Tiers and have a technical purpose.
We proceed by describing the different tiers in detail. Recall that in terms of realizability, Ordered Level Planarity is equivalent to the generalized version where and map to the reals. For the sake of convenience we will begin by designing in this generalized setting. It is easy to transform such that it satisfies the standard definition in a polynomialtime post processing step.
Tier 0 and 2, clause gadgets: The clause edges end in tier . It is composed of levels each of which contains precisely one vertex. We assign . Observe that this imposes no constraint on the order in which the edges enter .
Tier consists of a system of tunnels that resembles the monotone rectilinear representation of , see Figure 1(c). Intuitively it is constructed as follows: We take the top part of , rotate it by and place it to the left of the bottom part such that the variables’ line segments align, see Figure 1(b). We call the resulting representation . For each Eshape in we create a clause gadget, which is a subgraph composed of vertices that are placed on a grid close to the Eshape, see Figure 3. The red vertex at the bottom is the lower vertex of the clause edge of the clause corresponding to the Eshape. Without loss of generality we assume the grid to be fine enough such that the resulting ordered level graph can be drawn as in Figure 1(c) without crossings. Further, we assume that the coordinates of every pair of horizontal segments belonging to distinct Eshapes differ by at least . This ensures that all vertices on levels with width at least 3 have outdegree at most and indegree at most as stated in the lemma.
The clause gadget (without the clause edge) has a unique ordered level planar drawing in the sense that for every level the lefttoright sequence of vertices and edges intersected by the horizontal line through is identical in every ordered level planar drawing. This is due to the fact that the order of the topmost vertices , , , , and is fixed. We call the line segments , and the gates of . Note that the clause edge has to intersect one of the gates of . This corresponds to the fact the at least one literal of every clause has to be satisfied.
The subgraph induced by (without the clause edges) has a unique ordered level planar drawing. In tier we bundle all gates that belong to one literal together by creating two long paths for each literal. These two paths form the tunnel of the corresponding literal. All clause edges intersecting a gate of some literal have to be drawn inside the literal’s tunnel, see Figure 1(c). To this end, for we use () to refer to the leftmost (rightmost) vertex of a negative clause gadget placed on a line segment of representing . The vertices and are the first vertices of the paths forming the negative tunnel of the negative literal of variable . Analogously, we use () to refer to the leftmost (rightmost) vertex of a positive clause gadget placed on a line segment of representing . The vertices and are the first vertices of the paths forming the positive tunnel of the positive literal of variable . If for some the variable is not contained both in negative and positive clauses, we artificially add two vertices and or and on the corresponding line segments in order to avoid having to treat special cases in the remainder of the construction.
Tier 1 and 3, variable gadgets: Recall that every clause edge has to pass through a gate that is associated with some literal of the clause, and, thus, every edge is drawn in the tunnel of some literal. We need to ensure that it is not possible to use tunnels associated with the positive, as well as the negative literal of some variable simultaneously. To this end, we create a variable gadget with vertices in tier and tier for each variable. The variable gadget of variable is illustrated in Figure 3(a). The variable gadgets are nested in the sense that they start in in the order , from bottom to top and they end in the reverse order in , see Figure 5. We force all tunnels with index at least to be drawn between the vertices and . This is done by subdividing the tunnel edges on this level, see Figure 3(b). The long edge has to be drawn to the left or right of in . Accordingly, it is drawn to the left of or to the right of in . Thus, it is drawn either to the right (Figure 3(b)) of all the tunnels or to the left (Figure 3(c)) of all the tunnels. As a consequence, the blocking edge is also drawn either to the right or the left of all the tunnels. Together with the edge it prevents clause edges from being drawn either in the positive tunnel or negative tunnel of variable which end at level because they can not reach their endpoints in without crossings. We say or are blocked respectively.
The construction of the ordered level graph can be carried out in polynomial time. Note that maximum degree is and that all vertices on levels with width at least 3 have outdegree at most 1 and indegree at most 1 as claimed in the lemma.
Correctness: It remains to show that has an ordered level planar drawing if and only if is satisfiable. Assume that has an ordered level planar drawing . We create a satisfying truth assignment for . If is blocked we set to true, otherwise we set to false for . Recall that the subgraph induced by the vertices in tier has a unique ordered level planar drawing. Consider a clause and let be the indices of the variables whose literals are contained in . Clause edge has to pass level through one of the gates of . More precisely, it has to be drawn between either and , and or and if is negative or between either and , and or and if is positive, see Figure 1(c). First, assume that is negative and assume without loss of generality that it traverses between and . In this case clause edge has to be drawn in . Recall that this is only possible if is not blocked, which is the case if is false, see Figure 3(c). Analogously, if is positive and traverses w.l.o.g. between and , then is true, Figure 3(b). Thus, we have established that one literal of each clause in evaluates to true for our truth assignment and, hence, formula is satisfiable.
Now assume that is satisfiable and consider a satisfying truth assignment. We create an ordered level planar drawing of . It is clear how to create the unique subdrawing of . The variable gadgets are drawn in a nested fashion, see Figure 5. For we draw edge to left of and and edge to right of and . In other words, the pair is drawn between all such pairs with index smaller than . Recall that the vertices , , , and are located on higher levels than the according vertices of variables with index smaller than and that and are located on lower levels than the according vertices of variables with index smaller than .
For if is positive we draw the long edge to the right of and and, accordingly, we have to draw all tunnels left of and (except for , which has to be drawn to the left of and end to the right of ), see Figure 3(b). If is negative we draw the long edge to the left of and and, accordingly, we have to draw all tunnels right of and (except for , which has to be drawn to the right of and end to the left of ), see Figure 3(c). We have to draw the blocking edge to the right of if is positive and to the left of if is negative.
It remains to describe how to draw the clause edges.
Let be a clause. There is at least one true literal in . Let be the index of the corresponding variable. We describe the drawing of clause edge from bottom to top. We start by drawing in the tunnel () if is positive (negative). After the variable gadget of the edge leaves its tunnel and is drawn to the left (right) of all gadgets of variables with higher index, see Figure 5.
We obtain hardness for instances with maximum degree . In fact, we can restrict our attention to instances levelwidth . To this end, we split levels with width into levels containing exactly two vertices each.
Lemma 3
An instance of Ordered Level Planarity with maximum degree can be transformed in linear time into an equivalent instance of Ordered Level Planarity with levelwidth and maximum degree . If in all vertices on levels with width at least 3 have outdegree at most 1 and indegree at most 1, then . Otherwise, .
The reduction in Lemma 2 requires degree2 vertices. With , the problem becomes polynomialtime solvable. In fact, even if one can easily solve it as long as the maximum indegree and the maximum outdegree are both bounded by 1. Such instances consists of a set of monotone paths. We write , meaning that must be drawn to the left of , if and have vertices and that lie adjacent on a common level. If is acyclic, we can draw according to a linear extension of , otherwise there exists no solution.
Lemma 4
Ordered Level Planarity restricted to instances with maximum indegree and maximum outdegree can be solved in linear time.
For Ordered Level Planarity is solvable in linear time since Level Planarity can be solved in linear time [19]. Proper instances can be solved in lineartime via a sweep through every level. The problem is obviously contained in . The results of this section establish Theorem 1.1.
Acknowledgements: We thank the authors of [20] for providing us with unpublished information regarding their plane sweep approach for Manhattan Geodesic Planarity.
References
 [1] Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M., Rutter, I.: Beyond level planarity. In: Hu, Y., Nöllenburg, M. (eds.) Graph Drawing and Network Visualization  24th International Symposium, GD 2016, Athens, Greece, September 1921, 2016, Revised Selected Papers. Lecture Notes in Computer Science, vol. 9801, pp. 482–495. Springer (2016), URL http://dx.doi.org/10.1007/9783319501062_37
 [2] Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Roselli, V.: The importance of being proper: (in clusteredlevel planarity and tlevel planarity). Theor. Comput. Sci. 571, 1–9 (2015), URL http://dx.doi.org/10.1016/j.tcs.2014.12.019
 [3] Asinowski, A., Miltzow, T., Rote, G.: Quasiparallel segments and characterization of unique bichromatic matchings. Journal of Computational Geometry 6, 185–219 (2015)
 [4] Bachmaier, C., Brandenburg, F., Forster, M.: Radial level planarity testing and embedding in linear time. J. Graph Algorithms Appl. 9(1), 53–97 (2005), URL http://jgaa.info/accepted/2005/BachmaierBrandenburgForster2005.9.1.pdf
 [5] Bachmaier, C., Brunner, W.: Linear time planarity testing and embedding of strongly connected cyclic level graphs. In: Halperin, D., Mehlhorn, K. (eds.) Algorithms  ESA 2008, 16th Annual European Symposium, Karlsruhe, Germany, September 1517, 2008. Proceedings. Lecture Notes in Computer Science, vol. 5193, pp. 136–147. Springer (2008), URL http://dx.doi.org/10.1007/9783540877448_12
 [6] de Berg, M., Khosravi, A.: Optimal binary space partitions for segments in the plane. Int. J. Comput. Geometry Appl. 22(3), 187–206 (2012), URL http://www.worldscinet.com/doi/abs/10.1142/S0218195912500045
 [7] Brückner, G., Rutter, I.: Partial and constrained level planarity. In: Klein, P.N. (ed.) Proceedings of the TwentyEighth Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 1619. pp. 2000–2011. SIAM (2017), URL https://doi.org/10.1137/1.9781611974782
 [8] de Bruijn, N.G.: Problems 17 and 18. Nieuw Archief voor Wiskunde 2, 67 (1954), answers in Wiskundige Opgaven met de Oplossingen 20:19–20, 1955
 [9] Di Battista, G., Nardelli, E.: Hierarchies and planarity theory. IEEE Trans. Systems, Man, and Cybernetics 18(6), 1035–1046 (1988), URL http://dx.doi.org/10.1109/21.23105
 [10] Forster, M., Bachmaier, C.: Clustered level planarity. In: van Emde Boas, P., Pokorný, J., Bieliková, M., Stuller, J. (eds.) SOFSEM 2004: Theory and Practice of Computer Science, 30th Conference on Current Trends in Theory and Practice of Computer Science, Merin, Czech Republic, January 2430, 2004. Lecture Notes in Computer Science, vol. 2932, pp. 218–228. Springer (2004), URL http://dx.doi.org/10.1007/9783540246183_18
 [11] Fulek, R., Pelsmajer, M.J., Schaefer, M., Štefankovič, D.: Hanani–Tutte, monotone drawings, and levelplanarity. In: Thirty Essays on Geometric Graph Theory, pp. 263–287. Springer (2013)
 [12] Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31(2), 601–625 (2001), URL http://dx.doi.org/10.1137/S0097539794277123
 [13] Giacomo, E.D., Frati, F., Fulek, R., Grilli, L., Krug, M.: Orthogeodesic pointset embedding of trees. Comput. Geom. 46(8), 929–944 (2013), URL http://dx.doi.org/10.1016/j.comgeo.2013.04.003
 [14] Giacomo, E.D., Grilli, L., Krug, M., Liotta, G., Rutter, I.: Hamiltonian orthogeodesic alternating paths. J. Discrete Algorithms 16, 34–52 (2012), URL http://dx.doi.org/10.1016/j.jda.2012.04.012

[15]
Guibas, L.J., Yao, F.F.: On translating a set of rectangles. In: Proc. 12th Annual ACM Symposium Theory of Computing (STOC 1980). pp. 154–160 (1980)
 [16] Guibas, L.J., Yao, F.F.: On translating a set of rectangles. In: Preparata, F.P. (ed.) Computational Geometry, Advances in Computing Research, vol. 1, pp. 61–77. JAI Press, Greenwich, Conn. (1983)
 [17] Heath, L.S., Pemmaraju, S.V.: Recognizing leveledplanar dags in linear time. In: Brandenburg, F. (ed.) Graph Drawing, Symposium on Graph Drawing, GD ’95, Passau, Germany, September 2022, 1995, Proceedings. Lecture Notes in Computer Science, vol. 1027, pp. 300–311. Springer (1995), URL http://dx.doi.org/10.1007/BFb0021813
 [18] Jünger, M., Leipert, S., Mutzel, P.: Pitfalls of using PQtrees in automatic graph drawing. In: Battista, G.D. (ed.) Graph Drawing, 5th International Symposium, GD ’97, Rome, Italy, September 1820, 1997, Proceedings. Lecture Notes in Computer Science, vol. 1353, pp. 193–204. Springer (1997), URL http://dx.doi.org/10.1007/3540639381_62
 [19] Jünger, M., Leipert, S., Mutzel, P.: Level planarity testing in linear time. In: Whitesides, S. (ed.) Graph Drawing, 6th International Symposium, GD’98, Montréal, Canada, August 1998, Proceedings. Lecture Notes in Computer Science, vol. 1547, pp. 224–237. Springer (1998), URL http://dx.doi.org/10.1007/3540376232_17
 [20] Katz, B., Krug, M., Rutter, I., Wolff, A.: Manhattangeodesic embedding of planar graphs. In: Eppstein, D., Gansner, E.R. (eds.) Graph Drawing, 17th International Symposium, GD 2009, Chicago, IL, USA, September 2225, 2009. Revised Papers. Lecture Notes in Computer Science, vol. 5849, pp. 207–218. Springer (2009), URL http://dx.doi.org/10.1007/9783642118050_21
 [21] Wotzlaw, A., Speckenmeyer, E., Porschen, S.: Generalized kary tanglegrams on level graphs: A satisfiabilitybased approach and its evaluation. Discrete Applied Mathematics 160(1617), 2349–2363 (2012), URL http://dx.doi.org/10.1016/j.dam.2012.05.028
Appendix 0.A Omitted Proofs in Section 2
Lemma 1. Let with be a finite set of directions symmetric with respect to the origin. Ordered Level Planarity with maximum degree and levelwidth reduces to Geodesic Planarity such that the resulting instances are in general position and consist of a perfect matching and direction set . The reduction can be carried out using a linear number of arithmetic operations.
Proof
We first prove our claim for the classical case that contains exactly the four horizontal and vertical directions. Afterwards, we discuss the necessary adaptations for the general case. Our reduction is carried out in two steps. Let be an Ordered Level Planarity instance with maximum degree and levelwidth . In Step (i) we turn into an equivalent Geodesic Planarity instance . In Step (ii) we transform into an equivalent Geodesic Planarity instance where is a perfect matching and the vertex positions assigned via and are in general position.
Step (i): In order to transform into we apply a shearing transformation. We translate the vertices of each level by units to the right, see Figure 1(a) and Figure 1(b). Clearly, every geodesic drawing of can be turned into an ordered level planar drawing of . On the other hand, consider an ordered level planar drawing of . Without loss of generality we can assume that in all edges are realized as polygonal paths in which bend points occur only on the horizontal lines through the levels where . Further, we may assume that all bend points have coordinates in the open interval . We shear by translating the bend points and vertices of level by units to the right for , see Figure 1(b). In the resulting drawing , the vertex positions match those of . Furthermore, all edgesegments have a positive slope. Thus, since the maximum degree is we can replace all edgesegments with geodesic rectilinear paths that closely trace the segments and we obtain a geodesic drawing of , see Figure 1(c).
Step (ii): In order to turn into the equivalent instance we transform into a perfect matching. To this end, we split each vertex by replacing it with a small gadget that fits inside a square centered on the position of , see Figure 1(e). We call the square of and use , , and to denote the topright, topleft, bottomright and bottomleft corner of , respectively. We use two different sizes to ensure general position. The size of the gadget square is if and it is if . The gadget contains a degree1 vertex for every edge incident to . In the following we explain the gadget construction in detail, for an illustration see Figure 1(d). Let be an edge incident to . We create an edge where is a new vertex which is placed at if is located to the topright of and it is placed at if is located to the bottomleft of . Similarly, if is incident to a second edge , we create an edge where is placed at or depending on the position of . Finally, we create a blocking edge where is placed at and is placed at . The thereby assigned coordinates are in general position and the construction can be carried out in linear time.
Assume that has a geodesic drawing . By construction, all blocking edges have a topleft and a bottomright endpoint. On the other hand, all other edges have a bottomleft and a topright endpoint. As a result, a nonblocking edge can not pass through any gadget square , except the squares or since would have to cross the blocking edge of . Accordingly, it is straightforward to obtain a geodesic drawing of : We remove the blocking edges, reinsert the vertices of according to the mappings and and connect them to the vertices of their respective gadgets in a geodesic fashion. This can always be done without crossings. Figure 1(f) shows one possibility. If the edge from passes to the left of , we may have to choose a reflected version. Finally, we remove the vertices and which now act as subdivision vertices.
On the other hand, let be a geodesic planar drawing of . Without loss of generality, we can assume that each edge passes only through the squares of and . Furthermore, for each we can assume that its incident edges intersect the boundary of only to the topright of or to the bottomleft of , see Figure 1(g). Thus, we can simply remove the parts of the edges in the interior of the gadget squares and connect the gadget vertices to the intersection points of the edges with the gadget squares in a geodesic fashion.
The general case: It remains to discuss the adaptations for the case that
is an arbitrary set of directions symmetric with respect to the origin. By applying a linear transformation we can assume without loss of generality that
and are adjacent directions in . Accordingly, all the remaining directions point into the topleft or the bottomright quadrant. Further, by vertical scaling we can assume that no direction projects to on the unit square. Observe that if we do not insist on a coordinate assignment in general position, the reduction for the restricted case discussed above is already sufficient. In order to guarantee general position we have to avoid points that lie on a line with a direction from . This requires some easy but a bit technical modifications of our construction.Note that since no direction of points to the topright or bottomleft quadrant, every pair of conflicting vertices from that defines a line parallel to one of the directions in has to belong to one or both of the gadgets of two vertices with . Let and be the flattest and steepest slope of respectively. In order to guarantee general position we apply the following two changes.
(1) We increase the horizontal distance in the mapping between each pair of vertices and with and and in order to ensure that there can not be any conflicting vertices , in such that belongs to the gadget of and belongs to the gadget of . It suffices to translate and its square to the right such that is to the right of the line with direction through , see Figure 6(a).
(2) In order to ensure that there are no conflicting vertices , that belong to the same gadget square , we change the offset to the gadget square corners from and to and where is chosen small enough such that the gadget vertices are placed above the line with direction through , below the line with direction through , below the line with direction through and above the line with direction through , see Figure 6(b). ∎
Appendix 0.B Omitted Proofs in Section 3
Lemma 2. Planar Monotone 3Satisfiability reduces in polynomial time to Ordered Level Planarity. The resulting instances have maximum degree and all vertices on levels with width at least 3 have outdegree at most and indegree at most .
Proof
We perform a polynomialtime reduction from Planar Monotone 3Satisfiability. Let be a planar and monotone 3Satisfiability formula with . Let the variableclause graph of . Let be a monotone rectilinear representation of . We construct an ordered level graph such that has an ordered level planar drawing if and only if is satisfiable.
Overview: The ordered level graph has levels which are partitioned into four tiers , , and . Each clause is associated with a clause edge starting with in tier and ending with in tier . The clause edges have to be drawn in a system of tunnels that encodes the 3Satisfiability formula . In the layout of the tunnels corresponds directly to the rectilinear representation , see Figure 1(c). For each Eshape there are three tunnels corresponding to the three literals of the associated clause. The bottom vertex of each clause edge is placed such that has to be drawn inside one of the three tunnels of the Eshape corresponding to . This corresponds to the fact that in a satisfying truth assignment every clause has at least one satisfied literal. In tier we merge all the tunnels corresponding to the same literal. We create variable gadgets that ensure that for each variable edges of clauses containing can be drawn in the tunnel associated with either the negative or the positive literal of but not both. This corresponds to the fact that every variable is set to either true or false. Tiers and have a technical purpose.
We proceed by describing the different tiers in detail. Recall that in terms of realizability, Ordered Level Planarity is equivalent to the generalized version where and map to the reals. For the sake of convenience we will begin by designing in this generalized setting. It is easy to transform such that it satisfies the standard definition in a polynomialtime post processing step.
Tier 0 and 2, clause gadgets: The clause edges end in tier . It is composed of levels each of which contains precisely one vertex. We assign . Observe that this imposes no constraint on the order in which the edges enter .
Tier consists of a system of tunnels that resembles the monotone rectilinear representation of , see Figure 1(c). Intuitively it is constructed as follows: We take the top part of , rotate it by and place it to the left of the bottom part such that the variables’ line segments align, see Figure 1(b). We call the resulting representation . For each Eshape in we create a clause gadget, which is a subgraph composed of vertices that are placed on a grid close to the Eshape, see Figure 3. The red vertex at the bottom is the lower vertex of the clause edge of the clause corresponding to the Eshape. Without loss of generality we assume the grid to be fine enough such that the resulting ordered level graph can be drawn as in Figure 1(c) without crossings. Further, we assume that the coordinates of every pair of horizontal segments belonging to distinct Eshapes differ by at least . This ensures that all vertices on levels with width at least 3 have outdegree at most and indegree at most as stated in the lemma.
Technical Details: In the following two paragraphs, we describe the construction of the clause gadgets in detail.
For every where is negative we create its 11vertex clause gadget as follows, see Figure 3. Let be the three vertical line segments of the Eshape representing in where is leftmost and rightmost. Let be the lower endpoints and be the upper endpoints of , respectively. We place the tail of the clause edge of at . We create new vertices at , , , , , , and at which are the lattice points one unit to the right of , respectively. To simplify notation, we identify these new vertices with their locations on the grid. We add edges , , , , and to .
As stated above, we can assume without loss of generality that the grid is fine enough such that the resulting ordered level graph can be drawn as in Figure 1(c) without crossing. It suffices to assume that the horizontal and vertical distance between any two segment endpoints of is at least 3 (unless the endpoints lie on a common horizontal or vertical line).
Gates and Tunnels: The clause gadget (without the clause edge) has a unique ordered level planar drawing in the sense that for every level the lefttoright sequence of vertices and edges intersected by the horizontal line through is identical in every ordered level planar drawing. This is due to the fact that the order of the topmost vertices , , , , and is fixed. We call the line segments , and the gates of . Note that the clause edge has to intersect one of the gates of . This corresponds to the fact the at least one literal of every clause has to be satisfied.
The subgraph induced by (without the clause edges) has a unique ordered level planar drawing. In tier we bundle all gates that belong to one literal together by creating two long paths for each literal. These two paths form the tunnel of the corresponding literal. All clause edges intersecting a gate of some literal have to be drawn inside the literal’s tunnel, see Figure 1(c). To this end, for we use () to refer to the leftmost (rightmost) vertex of a negative clause gadget placed on a line segment of representing . The vertices and are the first vertices of the paths forming the negative tunnel of the negative literal of variable . Analogously, we use () to refer to the leftmost (rightmost) vertex of a positive clause gadget placed on a line segment of representing . The vertices and are the first vertices of the paths forming the positive tunnel of the positive literal of variable . If for some the variable is not contained both in negative and positive clauses, we artificially add two vertices and or and on the corresponding line segments in order to avoid having to treat special cases in the remainder of the construction.
Tier 1 and 3, variable gadgets: Recall that every clause edge has to pass through a gate that is associated with some literal of the clause, and, thus, every edge is drawn in the tunnel of some literal. We need to ensure that it is not possible to use tunnels associated with the positive, as well as the negative literal of some variable simultaneously. To this end, we create a variable gadget with vertices in tier and tier for each variable. The variable gadget of variable is illustrated in Figure 3(a). The variable gadgets are nested in the sense that they start in in the order , from bottom to top and they end in the reverse order in , see Figure 5. We force all tunnels with index at least to be drawn between the vertices and . This is done by subdividing the tunnel edges on this level, see Figure 3(b). The long edge has to be drawn to the left or right of in . Accordingly, it is drawn to the left of or to the right of in . Thus, it is drawn either to the right (Figure 3(b)) of all the tunnels or to the left (Figure 3(c)) of all the tunnels. As a consequence, the blocking edge is also drawn either to the right or the left of all the tunnels. Together with the edge it prevents clause edges from being drawn either in the positive tunnel or negative tunnel of variable which end at level because they can not reach their endpoints in without crossings. We say or are blocked respectively.
Technical Details: In the following two paragraphs, we describe the construction of the variable gadgets in detail.
Tier has layers each of which contains precisely one vertex. We refer to the vertex in layer as and to the vertex in layer as for . Tier has levels. In each of the levels , and where we create one vertex. These vertices are called , and respectively. In level we create two vertices and in this order. We add the edges ,
Comments
There are no comments yet.