Greedy Rectilinear Drawings

Abstract

A drawing of a graph is greedy if for each ordered pair of vertices u and v, there is a path from u to v such that the Euclidean distance to v decreases monotonically at every vertex of the path. The existence of greedy drawings has been widely studied under different topological and geometric constraints, such as planarity, face convexity, and drawing succinctness. We introduce greedy rectilinear drawings, in which each edge is either a horizontal or a vertical segment. These drawings have several properties that improve human readability and support network routing. We address the problem of testing whether a planar rectilinear representation, i.e., a plane graph with specified vertex angles, admits vertex coordinates that define a greedy drawing. We provide a characterization, a linear-time testing algorithm, and a full generative scheme for universal greedy rectilinear representations, i.e., those for which every drawing is greedy. For general greedy rectilinear representations, we give a combinatorial characterization and, based on it, a polynomial-time testing and drawing algorithm for a meaningful subset of instances.

This work started at the Bertinoro Workshop on Graph Drawing 2017, Italy. Research was partially supported by DFG grant Ka812/17-1 and by the project “Algoritmi e sistemi di analisi visuale di reti complesse e di grandi dimensioni” - Ricerca di Base 2018, Dipartimento di Ingegneria dell’Università degli Studi di Perugia.

1 Introduction

In a greedy drawing of a graph in the plane every vertex is mapped to a distinct point and, for each ordered pair of vertices u and v, there is a distance-decreasing path from u to v, i.e., a path such that the Euclidean distance to v decreases monotonically at every vertex of the path. Greedy drawings have been originally proposed to support greedy routing schemes for ad hoc wireless networks [20,21,22]. In such schemes, a node that has to send a packet to a destination v just forwards the packet to one of its neighbors that is closer to v than itself. In their seminal work, Papadimitriou and Ratajczak [20, 21] showed that 3-connected planar graphs form the largest class of graphs for which every instance may admit a greedy drawing, and they formulated two conjectures. Weak conjecture: Every 3-connected planar graph admits a greedy drawing. Strong conjecture: Every 3-connected planar graph admits a convex greedy drawing, i.e., a planar greedy drawing with convex faces. Concerning the weak conjecture, Dhandapani [8] provided an existential proof of greedy drawings for maximal planar graphs. Later on, Leighton and Moitra [16] and Angelini et al. [4] independently settled the weak conjecture positively, by also describing constructive algorithms. Da Lozzo et al. [7] strengthened these results, showing that in fact every 3-connected planar graph admits a planar greedy drawing. However, the strong conjecture is still open. For graphs that are not 3-connected, Nöllenburg and Prutkin [18] characterized the trees that admit a greedy drawing.

Greedy drawings have also been investigated in terms of succinctness, an important property that helps to make greedy routing schemes work in practice. A drawing is succinct if the vertex coordinates are represented by a polylogarithmic number of bits. Since there exist greedy-drawable graphs in the Euclidean sense that do not admit a succinct greedy drawing [3], several papers also studied succinct greedy drawings in spaces different from the Euclidean one or according to a metric different from the Euclidean distance [11,12,13,14, 17, 24].

We finally mention another model, called self-approaching drawing, that reinforces the properties of greedy drawings [1, 19]. A straight-line drawing is self-approaching if for any ordered pair of vertices u and v, there exists a path P from u to v such that, for any point p on P, the distance from u to p always decreases while continuously moving along P in the drawing. Clearly, every self-approaching drawing is greedy, but not vice versa. In particular, the dilation of self-approaching drawings is bounded by a constant [15], while for greedy drawings it may be unbounded [1]. The dilation (or “stretch-factor”) of a straight-line drawing is the maximum value of the ratio between the length of the shortest path between two vertices in the drawing and their Euclidean distance.

Motivation and Contribution. Our work is motivated by the rich literature on greedy drawings that satisfy some interesting topological or geometric requirements, such as planarity [7] and face convexity [13, 14, 20, 24]. We study greedy drawings in the popular orthogonal drawing convention [9, 10, 23]: Vertices are mapped to points and edges are sequences of horizontal and vertical segments (each vertex has degree at most 4). More precisely, we introduce planar greedy rectilinear drawings, that is, crossing-free greedy drawings where each edge is either a horizontal or a vertical segment. We address the following question: “Let H be a planar rectilinear representation, i.e., a plane graph with given values ($90^\circ$, $180^\circ$, $270^\circ$) for the geometric angles around each vertex; is it possible to assign coordinates to the vertices of H so that the resulting drawing is greedy rectilinear?”. Figure 1a shows a rectilinear drawing that is not greedy; however, the corresponding rectilinear representation has a greedy drawing, as shown in Fig. 1b. Our question fits into the effective topology-shape-metrics approach [5, 23], which first computes a planar embedding of the graph, then finds an embedding-preserving orthogonal representation, and finally assigns coordinates to vertices and bends to complete the drawing; we address this last step, but our representations have no bend. Our contribution is as follows.

Fig. 1.

(a) A rectilinear drawing that is not greedy; (b) A greedy rectilinear drawing of the same representation (the distance-decreasing paths between u and v are dashed). (c) Drawing of a universal greedy rectilinear representation. (d)–(e) H is not greedy realizable if an internal face is not a rectangle or the external face is not orthoconvex.

Section 2 discusses basic properties of greedy rectilinear drawings. We prove that the faces are convex and the dilation is bounded by a small constant, and we show convex (non-rectilinear) greedy drawings in which every distance-decreasing path between two nodes is arbitrarily longer than the Euclidean distance.

Section 3 focuses on planar universal greedy rectilinear representations for which every drawing is greedy (see Fig. 1c). We give a linear-time recognition algorithm that, in the positive case, computes a greedy drawing of minimum area on an integer grid. We also describe a generative scheme for constructing any possible universal greedy rectilinear representation starting from a rectangle.

Section 4 extends the study to general rectilinear greedy representations. We give a non-geometric characterization of this class, which leads to a linear-time testing algorithm for a meaningful subset of instances. If the condition of the characterization is satisfied, a greedy drawing of minimum area within that condition can be computed in quadratic time. However, we show that in general greedy rectilinear representations may require exponential area.

We assume familiarity with basic concepts of graph drawing and planarity [9]; for space reasons, terminology and some proofs are moved to the full version [2].

2 Basic Properties of Greedy Rectilinear Representations

We denote by x(v) and y(v) the x- and the y-coordinate of a vertex v in a drawing $\varGamma$ of a graph. For two vertices u and v of $\varGamma$, d(u, v) is the Euclidean distance between u and v and a path from u to v in $\varGamma$ is a u-v-path. The degree of v is denoted as $\deg (v)$. If v has neighbors $u_1, u_2, \dots , u_h$, the cell of v in $\varGamma$, denoted as $\mathrm {cell}(v)$, is the (possibly unbounded) region of all points of the plane that are closer to v than to any $u_i$. Figure 2 shows all types of cells of a vertex v in a rectilinear drawing, depending on $\deg (v)$ and on the angles at v; if $\deg (v) \le 3$, $\mathrm {cell}(v)$ is unbounded. The following geometric characterization is proven in [21].

Theorem 1

(Papadimitriou and Ratajczak [21]). A drawing of a graph is greedy if and only if for every vertex v, $\mathrm {cell}(v)$ contains no vertex other than v.

Fig. 2.

Different types of cells (shaded regions) of a vertex v in a rectilinear drawing of a graph: (a) $\deg (v)=4$; (b) $\deg (v)=3$; (c)–(d) $\deg (v)=2$, (e) $\deg (v)=1$.

If a rectilinear representation H admits a greedy rectilinear drawing, H is greedy realizable or, equivalently, it is a greedy rectilinear representation. W.l.o.g., we shall assume that H comes with a fixed “rotation”, i.e., for any edge (u, v), it is fixed whether u is to the left, to the right, above, or below v in every rectilinear drawing $\varGamma$ of H. A flat vertex of H (or of $\varGamma$) is a vertex with a flat angle ($180^\circ$). A flat angle formed by two horizontal segments is north-oriented (south-oriented) if it is above (below) the two segments. A flat angle between two vertical segments is either east-oriented or west-oriented.

We restrict our study to biconnected graphs, as otherwise the set of greedy rectilinear drawings may be very limited (see the full version [2]). Lemma 1 (proved in the full version [2]) allows us to further restrict to convex rectilinear representations, i.e., those having rectangular internal faces and an orthoconvex polygon as external boundary. Indeed, if H is not convex, there exist two vertices u, v such that $u \in \mathrm {cell}(v)$ in any drawing of H (see also Figs. 1d–e).

Lemma 1

H is greedy realizable only if it is convex.

For a rectilinear drawing of a convex rectilinear representation H, let R(u, v) denote the minimum bounding box (rectangle or segment) including u and v. The next property immediately follows from the convexity of H.

Property 1

Let f be a face of H and w be any vertex of H with an angle of $90^\circ$ inside f. Denote by u and v the two neighbors of w along the boundary of f. In any rectilinear drawing of H, there is no vertex properly inside R(u, v).

We exploit Property 1 to prove that rectilinear greedy drawings have bounded dilation, where the paths that determine the dilation are distance-decreasing. An analogous statement does not hold for general convex greedy drawings; an example of this fact is in the full version [2], together with the proof of Theorem 2.

Theorem 2

In a rectilinear greedy drawing on an integer grid, for every two vertices s, t there is a distance-decreasing s-t-path of length at most $3 \sqrt{2} \cdot d(s,t)$.

Conflicts in Rectilinear Representations. We now define two directed acyclic graphs (DAGs) $D_x$ and $D_y$ associated with H, already used for orthogonal compaction [6, 23]. They are fundamental tools for the rest of the paper. $D_x$ is obtained from H by orienting the horizontal edges from left to right and by contracting each maximal path of vertical edges into a node. $D_y$ is defined symmetrically on the maximal paths of horizontal edges; see Fig. 3. $D_x$ and $D_y$ may have multiple edges and they are st-digraphs (they have a single source and a single sink), since the external face of H is orthoconvex. For any vertex u of H, we denote by $c_x(u)$ ($c_y(u)$) the node of $D_x$ ($D_y$) corresponding to the maximal vertical (horizontal) path containing u in H. If , the notation $u \prec _x v$ () denotes the existence (absence) of a directed path from $c_x(u)$ to $c_x(v)$ in $D_x$. The notation $u \sim _x v$ means that either $u \prec _x v$ or $v \prec _x u$ holds, while means that none of them holds. The notations $u \prec _y v$, , $u \sim _y v$, and are symmetric for $D_y$. Clearly, $\prec _x$ and $\prec _y$ are transitive relations. The next lemma (proved in the full version [2]) states that there is a directed path between any two vertices of H in at least one of $D_x$ and $D_y$.

Fig. 3.

(a) A greedy realizable convex rectilinear representation H that is not universal greedy due to conflict $\{u,v\}$; (b)–(c) The DAGs $D_x$ and $D_y$ for H. (d) A non-convex representation such that $u \in \mathrm {cell}(v)$ for any drawing, even though $u \prec _x v$ and $u \prec _y v$.

Lemma 2

For any two vertices u and v of a convex rectilinear representation H, at least one of the following holds: (i) $u \sim _x v$ or (ii) $u \sim _y v$.

Let u and v be two vertices of H such that and . By Lemma 2, at least one of $u \sim _x v$ and $u \sim _y v$ holds, say the latter. If $u \sim _x v$ also holds, the relative positions (left/right/top/bottom) of u and v are fixed (they are the same in any drawing of H); in this case, we prove that none of the two vertices lies in the cell of the other in any drawing of H (Lemma 3). Conversely, this is not guaranteed if (Theorem 3), and we say that u and v are in a conflict, denoted by $\{u,v\}$. In this case, suppose that $u \prec _y v$ (the case $v \prec _y u$ is symmetric) and consider the topmost (flat) vertex $u'$ of the vertical path corresponding to $c_x(u)$ and the bottommost (flat) vertex $v'$ of the vertical path corresponding to $c_x(v)$. We say that $u'$ and $v'$ are responsible for the conflict $\{u,v\}$. A conflict $\{u,v\}$ is an x-conflict if and a y-conflict if . In Fig. 3a, $\{u,v\}$ is an x-conflict, with $u'=u$ and $v'=v$. A conflict is resolved in a drawing $\varGamma$ of H if none of the two vertices that are responsible for it lies in the cell of the other. The proof of Lemma 3 is in the full version [2].

Lemma 3

Let H be a convex rectilinear representation of a biconnected graph. A rectilinear drawing $\varGamma$ of H is greedy if and only if every conflict is resolved  in $\varGamma$.

3 Universal Greedy Rectilinear Representations

A convex rectilinear representation H is conflict-free if it has no conflict. The following concise characterization holds for universal rectilinear representations.

Theorem 3

Let H be a convex rectilinear representation of a biconnected plane graph. H is universal greedy if and only if it is conflict-free.

Proof

By Lemma 3, if H is conflict-free, every rectilinear drawing of H is greedy (note that a rectilinear representation may be conflict-free without being convex, which would imply that it is not universal greedy; see Fig. 3d).

Suppose that H is universal greedy but not conflict-free. Let $\varGamma$ be any rectilinear drawing of H. Consider two vertices u and v that are responsible for a conflict in H; assume w.l.o.g. that . We can further assume that there is no vertex w such that $x(u)< x(w) < x(v)$ in $\varGamma$. Indeed, if such a vertex w exists (which implies and ), at least one of and holds, as otherwise $u \prec _x v$. Hence, we could have selected either u and w or w and v instead of u and v. If $x(u) = x(v)$, $\varGamma$ is not greedy, because $u \in \mathrm {cell}(v)$ and $v \in \mathrm {cell}(u)$. If $x(u) < x(v)$, we can transform $\varGamma$ into a drawing $\varGamma '$ by moving u and all the vertices in its vertical path to the right until $x(u)=x(v)$. Since u and v are consecutive along the x-axis in $\varGamma$ and since H is convex, $\varGamma '$ is still planar but not greedy, which contradicts the fact that H is universal greedy.    $\square$

Theorem 4

Let H be a rectilinear representation of an n-vertex biconnected plane graph. There exists an O(n)-time algorithm to test if H is universal greedy.

Proof

The algorithm first checks in linear time if H is convex. If not, the instance is rejected. Otherwise, it checks whether both $D_x$ and $D_y$ contain a (directed) Hamiltonian path, which can be done in linear time in the size of $D_x$ and $D_y$, which is O(n). Namely, since each of $D_x$ and $D_y$ is an st-digraph, computing a longest path from s to t is done in O(n) time from a topological sorting. We claim that H is universal greedy if and only if this test succeeds. By Theorem 3, to prove this claim, it is enough to show that a DAG D contains a Hamiltonian path if and only if for any two vertices u and v of D, there is a directed path either from u to v or from v to u. If D has a Hamiltonian path $\pi$, a directed path between any two vertices of D is a subpath of $\pi$. Conversely, if there is a directed path between any two vertices of D, then a linear extension of a topological sorting of the vertices corresponds to a Hamiltonian path.    $\square$

Since conflict-free rectilinear representations are a subclass of the turn-regular orthogonal representations [6], for which a minimum-area drawing can be found in linear time, we can also state the following.

Corollary 1

Let H be a universal greedy rectilinear representation. There is a linear-time algorithm to compute a (greedy) drawing of H with minimum area.

Generative Scheme. Let H be a biconnected universal greedy rectilinear representation. Each of the following operations on H produces a new biconnected universal greedy rectilinear representation, which gives a generative scheme for universal greedy rectilinear representations. The proof is in the full version [2].

− k-reflex vertex addition. Attach to the external face of H a path of $1 \le k \le 4$ reflex vertices (corners) that forms a new rectangular internal face, provided that the resulting representation is convex.

− flat vertex addition. Subdivide an external edge (u, v) of H with a flat vertex of degree two, provided that the strip of the plane between the two lines orthogonal to (u, v) and passing through u and v, respectively, has no vertices in its interior.

Theorem 5

Let H be a universal greedy rectilinear representation of a biconnected planar graph. H can be obtained by a suitable sequence of k-reflex vertex and flat vertex additions, starting from a rectangle.

4 General Greedy Rectilinear Representations

We now consider convex rectilinear representations H of biconnected plane graphs that may contain conflicts, and investigate conditions under which they are greedy realizable. We present a characterization (Theorem 6), which yields a polynomial-time testing algorithm for a meaningful subclass of instances, namely when $D_x$ and $D_y$ are series-parallel (Theorem 9). Proofs are in the full version [2].

Let D be one of the two DAGs $D_x$ and $D_y$ associated with H. Since D is an st-digraph, it has an st-ordering $\mathcal {S} = v_1, \dots , v_m$. For two indices i, j, with $1 \le i < j \le m$, $D\langle i,j\rangle$ denotes the subgraph of D induced by $v_i, \dots , v_j$. We say that $\mathcal {S}$ is good if: (S.1) For any two indices i, j, with $1 \le i < j \le m$, $D\langle i,j\rangle$ has at most two connected components, and (S.2) if $D\langle i,j\rangle$ has exactly two components, then all nodes of one component precede those of the other in $\mathcal {S}$.

Further, we say that a drawing of H respects an st-ordering $\mathcal {S}_x$ of $D_x$ ($\mathcal {S}_y$ of $D_y$) if for any two vertices $u, w \in H$, we have that u lies to the left of w (below w) in the drawing if and only if $c_x(u)$ precedes $c_x(w)$ in $\mathcal {S}_x$ ($c_y(u)$ precedes $c_y(w)$ in $\mathcal {S}_y$). Finally, when we refer to the x-coordinate (y-coordinate) of a node $v_i$ of $D_x$ (of $D_y$), we mean the one of all the vertices $w \in H$ with $c_x(w) = v_i$ (with $c_y(w) = v_i$), as these vertices belong to the same vertical (horizontal) path.

Theorem 6

A convex rectilinear representation H of a biconnected plane graph is greedy realizable if and only if both DAGs $D_x$ and $D_y$ admit good st-orderings.

We start by proving the necessity of Theorem 6.

Lemma 4

If $D_x$ or $D_y$ admits no good st-ordering, H is not greedy realizable.

Proof Sketch

If H admits a greedy drawing $\varGamma$ respecting an st-ordering $\mathcal {S}_x$ of $D_x$ that is not good, there exist i, j, with $1 \le i < j \le m$, such that $D_x\langle i,j\rangle$ has at least two connected components $C_1$ and $C_2$. First, note that the vertices of $C_1$ and $C_2$ are vertically separated by a horizontal line in $\varGamma$ (say, $C_1$ lies above $C_2$; see Fig. 4), as otherwise there would be at least a pair of vertical paths whose corresponding nodes in $D_x$ are joined by a directed path.

Fig. 4.

Illustration for the proof of Lemma 4

Since every internal face of H is rectangular, the vertices of the bottom (top) boundary of $C_1$ ($C_2$) are part of a horizontal path, spanning all x-coordinates between the ones of $v_i$ and $v_j$. Thus, all vertices on the bottom (top) boundary of $C_1$ ($C_2$) are south-oriented (north-oriented) flat vertices, and the union of their cells is a connected region spanning all the x-coordinates between their leftmost and rightmost vertices; see Fig. 4a. So, if a vertex of $C_1$ appears between two vertices of $C_2$ in $\mathcal {S}_x$, then it lies inside the cell of a vertex of $C_2$ in $\varGamma$, and vice versa. Thus, the vertices of each component are consecutive in $\mathcal {S}_x$. Since $\mathcal {S}_x$ is not good, there is at least another component $C_3$ in $D_x\langle i,j\rangle$; see Fig. 4b. Consider the vertical line $\ell$ that is horizontally equidistant to $v_i$ and $v_j$ in $\varGamma$. Any two components of $D_x\langle i,j\rangle$ must be separated by $\ell$ in order for the cells of the vertices of these components to be empty, which is not possible for three components.    $\square$

To prove the sufficiency of Theorem 6, we assign the x- and y-coordinates in two steps, which can be performed independently due to the following lemma.

Lemma 5

Let $\varGamma _1$ and $\varGamma _2$ be two drawings of H such that all x-conflicts are resolved in $\varGamma _1$ and all y-conflicts are resolved in $\varGamma _2$. Then, the drawing $\varGamma _3$ of H in which the x-coordinate of each vertex is the same as in $\varGamma _1$ and the y-coordinate of each vertex is the same as in $\varGamma _2$ is greedy.

We describe the assignment of the x-coordinates based on the good st-ordering $\mathcal S_x=v_1,\ldots ,v_m$ of $D_x$. The assignment of the y-coordinates based on the good st-ordering of $D_y$ works symmetrically. We first prove in Lemma 6 that, to guarantee that every x-conflict is resolved, it suffices to resolve a specific subset of them, which is called minimal. Namely, an x-conflict $\{u,v\}$ dominates an x-conflict $\{w,z\}$, with $c_x(u)=v_i$, $c_x(v)=v_j$, $c_x(w)=v_k$, and $c_x(z)=v_\ell$, if $k\le i<j\le \ell$. A minimal x-conflict is not dominated by any x-conflict.

By Lemmas 3 and 6, we conclude that a greedy rectilinear drawing can be obtained by resolving all the minimal conflicts. We finally give a constructive proof that this can always be done since $\mathcal S_x$ is good. In particular, we encode that a minimal x-conflict is resolved with a single inequality on the horizontal distances between the vertices in the x-conflict. Then, in Lemma 7, we prove that for a minimal x-conflict $\{u,v\}$ the nodes $c_x(u)$ and $c_x(v)$ of $D_x$ are consecutive in $\mathcal S_x$. We use this property to show that the system of inequalities describing the conditions for the minimal x-conflicts to be resolved always admits a solution.

Lemma 6

Let $\varGamma$ be a rectilinear drawing of H respecting $\mathcal {S}_x$. If every minimal x-conflict dominating an x-conflict $\{u,w\}$ is resolved in $\varGamma$, $\{u,w\}$ is resolved.

Proof Sketch

We may assume that u and w are responsible for $\{u,w\}$. Let $v_i = c_x(u)$ and $v_j = c_x(w)$, with $i < j$. Since $\mathcal S_x$ is good, graph $D_x\langle i,j \rangle$ has at most two connected components $C_1$ and $C_2$. Assume that $v_i \in C_1$.

Suppose first that $v_j \in C_1$. Let $u'$ be the right neighbor of u in H; see Fig. 5a. Since $v_i,v_j \in C_1$, node $c_x(u')$ precedes $c_x(w)$ in $\mathcal {S}_x$ and $c_x(u') \in C_1$. So, $u'$ lies to the left of w in any drawing of H respecting $\mathcal {S}_x$. Hence, the mid-point of edge $(u,u')$, which defines the right boundary of $\mathrm {cell}(u)$, l ies to the left of w, and thus . Symmetrically, .

Fig. 5.

Illustration for the proof of Lemma 6

Suppose now that $v_j \in C_2$. By symmetry, we assume that $C_1$ lies above and to the left of $C_2$; see Fig. 5b. Let z (r) be the bottommost (topmost) vertex of the vertical path corresponding to the last node $c_x(z)$ of $C_1$ (first node $c_x(r)$ of $C_2$) in $\mathcal S_x$, i.e., z and r are responsible for a minimal (and thus resolved) x-conflict.

We show that (by symmetry, ). If $u' \in C_1$, the previous case applies. Otherwise, u lies on the right boundary of $C_1$. If $c_x(u)$ is a sink of $C_1$, then $C_1$ contains only $c_x(u)$; see Fig. 5c. Thus, either $c_x(u)$ is not a sink of $C_1$, or $c_x(u)=c_x(z)$. In the latter case, , since the minimal x-conflict $\{z,r\}$ is resolved, which implies . Hence,  and $c_x(u)$ is not a sink of $C_1$; see Fig. 5d. Since and u is south-oriented, u lies below z. Let $z'$ be the right neighbor of z, with $c_x(z')=v_k$. If $z'$ is to the left of $u'$, $D_x\langle i,k \rangle$ has two connected components; one contains $v_i$ and $v_k$, the other contains $v_j$, as $(u,u')$ cannot be crossed. This contradicts (S.2), as $i<j<k$. So, $z'$ is to the right of $u'$. Since z is to the right of u, the right boundary of $\mathrm {cell}(z)$ is to the right of the one of $\mathrm {cell}(u)$. Since , also , and thus .    $\square$

Lemma 7

For any two vertices u and w of H such that $\{u,w\}$ is a minimal x-conflict, we have that $c_x(u)$ and $c_x(w)$ are consecutive in a good st-ordering $\mathcal {S}_x$.

Proof

Suppose that there is a vertex $z \in H$ such that $c_x(z) = v_j$ lies between $c_x(u) = v_i$ and $c_x(w) = v_k$ in $\mathcal {S}_x$, i.e., $i< j < k$. If $c_x(u)$ and $c_x(w)$ belong to the same connected component C of $D_x\langle i,k\rangle$, then by definition, $v_i$ and $v_k$ are a source and a sink of C, respectively. Since $\{u, w\}$ is an x-conflict, we have ; hence, there is another source $c_x(s)$ in C, for some vertex $s \in H$, such that $s \prec _x w$. Since $c_x(u)$ and $c_x(s)$ are different sources of C, we have , and thus $\{u,s\}$ is an x-conflict dominating the minimal x-conflict $\{u,w\}$; a contradiction. If $c_x(u)$ and $c_x(w)$ belong to different components, then $c_x(z)$ does not belong to the same component as one of them, say $c_x(u)$. Thus, , i.e., $\{u,z\}$ is an x-conflict dominating $\{u,w\}$; a contradiction.    $\square$

We now present our algorithm to assign x-coordinates so that all minimal x-conflicts are resolved. We extend some definitions from vertices of H to nodes of $D_x$. Namely, we say $v_i\prec _x v_j$ if there is a directed path in $D_x$ from $v_i$ and $v_j$. Also, we say that there is a (minimal) x-conflict $\{v_i,v_j\}$ in $D_x$ if there is a (minimal) x-conflict $\{u,w\}$ in H such that $c_x(u)=v_i$ and $c_x(w)=v_j$.

For $0<i,j\le m$, let $x_{i,j}:=x_{j}-x_i$ be the x-distance between $v_i$ and $v_j$. To prove that a good st-ordering $\mathcal {S}_x$ allows for a greedy realization, we set up a system of inequalities describing the geometric requirements for the x-distance of consecutive nodes in $\mathcal {S}_x$ in a greedy drawing, and then prove that this system always admits a solution since $\mathcal {S}_x$ is good. First note that, for every $0<i<m$ such that there is no minimal x-conflict $\{v_i,v_{i+1}\}$, we only require the x-distance to be positive, so we define the trivial inequality $x_{i,i+1}>0$.

For every $0<i<m$ such that there is a minimal x-conflict $\{v_i,v_{i+1}\}$, we define two inequalities that describe the necessary conditions for the x-conflict to be resolved. Let u and w, with $c_x(u)=v_i$ and $c_x(w)=v_{i+1}$, be responsible for $\{v_i,v_{i+1}\}$. We assume that $u \prec _y w$; the other case is symmetric.

Fig. 6.

Solving the inequalities of $x_{i,i+1}$ implies  and .

Fig. 7.

The relation graph defined by the left and right inequalities

By assumption, $v_i$ lies to the bottom left of $v_{i+1}$, so we only have to consider the part $\mathrm {cell}_{\swarrow }(w)$ of $\mathrm {cell}(w)$ to the bottom left of w (dark region in Fig. 6). Let $(w',w)$ be the bottommost incoming edge of $v_{i+1}$ with $c_x(w')=v_{\ell _{i+1}}$. Then, the left boundary of $\mathrm {cell}_{\swarrow }(w)$ is delimited by the vertical line through the mid-point of $(w',w)$. Thus, we require $x_{i,i+1}>x_{\ell _{i+1},i+1}/2\Leftrightarrow x_{i,i+1}>x_{{\ell _{i+1}},i}$. Symmetrically, we only consider the part $\mathrm {cell}_{\nearrow }(u)$ of $\mathrm {cell}(u)$ to the top right of u (light region in Fig. 6), which is bounded by the vertical line through the mid-point of the topmost outgoing edge $(u,u')$ of $v_i$ with $c_x(u')=v_{r_i}$. Thus, we require $x_{i,i+1}>x_{i,{r_i}}/2\Leftrightarrow x_{i,i+1}>x_{i+1,{r_i}}$. Since $v_{\ell _{i+1}}$ and $v_i$ (and $v_{i+1}$ and $v_{r_i}$) are not necessarily consecutive in the st-ordering, we express the x-distance $x_{{\ell _{i+1}},i}$ (and $x_{i,{r_i}}$) as the sum of the x-distances between the consecutive nodes between them in the st-ordering. This gives the left and the right inequality.

$$\begin{aligned} x_{i,i+1}>\sum _{j={\ell _{i+1}}}^{i-1}x_{j,j+1}&\quad \text {(left inequality)}&x_{i,i+1}>\sum _{j=i+1}^{{r_i}-1}x_{j,j+1}&\quad \text {(right inequality)} \end{aligned}$$

Note that for every variable $x_{i,i+1}$ there exists either a trivial inequality or a left and right inequality. Consider the following triangulated matrices, where $c_{i,j}=-1$ if $i>j\ge \ell _{i+1}$ or $i<j\le r_i$, where $c_{i,j}=1$ if $i=j$, and $c_{i,j}=0$ otherwise.

We express the left and trivial (right and trivial) inequalities as $Ax>0$ (as $Bx>0$). Any vector $x>0$ determines a unique rectilinear drawing: we assign to each vertex the y-coordinate defined by $S_y$, we assign to $v_1$ the x-coordinate $x_1=0$ and to every other $v_i$ the x-coordinate $x_{i}=x_{i-1}+x_{i-1,i}$. Since $x>0$, the x-coordinates preserve the good st-ordering and resolve all x-conflicts.

Lemma 8

A vector $x=(x_{1,2},\ldots ,x_{m-1,m})^\top >0$ solves both $Ax>0$ and $Bx>0$ if and only if it determines a drawing where all x-conflicts are resolved.

Note that we can always solve $Ax>0$ and $Bx>0$ independently by solving the linear equation systems $Ax=1$ and $Bx=1$ via forward substitution, since A and B are triangular. We prove that there is always a vector x solving $Ax>0$ and $Bx>0$ simultaneously. Let $C=A+B-I_{m-1}$ be the matrix defined by the values of $c_{i,j}$. Any solution to the linear inequality system $Cx>0$ is also a solution to both $Ax>0$ and $Bx>0$. We show that C can be triangulated. For this, we define the relation graph corresponding to the adjacency matrix $I_{m-1}-C$ that contains a vertex $u_i$ for each interval $x_{i,i+1}$, $1\le i<m$, and a directed edge from a vertex $u_i$ to a vertex $u_j$ if and only if $c_{i,j}=-1$; see Fig. 7.

Lemma 9

The relation graph of a good st-ordering is acyclic.

Proof Sketch

We show that a shortest cycle $\mathcal C$ in the relation graph has length 2, finding a “shortcut” for every longer cycle. Then, we analyze the relative order of the y-coordinates of the responsible vertices for the two minimal x-conflicts in H corresponding to $\mathcal C$, and find a contradiction for every combination.    $\square$

Lemma 10

The matrix C is triangularizable.

Proof

By Lemma 9, the relation graph described by the matrix $I_{m-1}-C$ is acyclic. Hence, there is a permutation matrix P (corresponding to a topological sort) such that $P(I_{m-1}-C)P^{-1}$ is triangulated with only 0’s on the diagonal. Thus, $PI_{m-1}P^{-1}-PCP^{-1}=I_{m-1}-PCP^{-1}$ is triangulated with only 0’s on the diagonal, so $PCP^{-1}$ is triangulated with only 1’s on the diagonal.    $\square$

Since C is triangularizable by Lemma 10, the system of linear equations $Cx=1$ always has a solution, which solves $Ax>0$ and $Bx>0$ simultaneously. This concludes the sufficiency proof for Theorem 6.

Note that the given construction ensures that all the coordinates are integer; however, the area of the drawing is in general not minimum. A rectilinear greedy drawing with minimum area respecting the given st-orderings can be constructed in polynomial time by solving a linear program that minimizes $\sum _{i=1}^{m-1} x_{i,i+1}$ under the constraints $Ax\ge 1$ and $Bx\ge 1$. We analyze the integrality of the solution and the running time in the full version [2].

Theorem 7

Let H be a convex rectilinear representation of a biconnected plane graph and let $\mathcal S_x$ and $\mathcal S_y$ be good st-orderings of $D_x$ and $D_y$. We can compute a greedy drawing of H that respects $\mathcal S_x$ and $\mathcal S_y$ with minimum area in $O(n^2)$ time.

Fig. 8.

Exponential area lower bound

Although minimum, the area of the drawings yielded by our algorithm may be non-polynomial in some cases; Theorem 8 states that there exist convex rectilinear representations (see Fig. 8) whose DAGs admit good st-orderings, but there is no combination of them resulting in a succinct greedy drawing, since the solutions of the corresponding system of inequalities are always exponential in the input size. On the contrary, every universal greedy rectilinear representation of an n-vertex graph is succinct, since by Corollary 1 it has a (greedy) drawing of minimum area on an integer grid of size $O(n^2$) [6, 23].

Theorem 8

There exist rectilinear representations whose every greedy rectilinear drawing has exponential area, even if $D_x$ and $D_y$ are series-parallel.

When $D_x$ and $D_y$ are series-parallel, the conditions can be tested efficiently.

Theorem 9

Let H be a convex rectilinear representation of a biconnected plane graph. If $D_x$ and $D_y$ are series-parallel, we can test in O(n) time if H is greedy realizable. If the test succeeds, a greedy drawing of H is computed in $O(n^2)$ time.

Proof Sketch

To find a good st-ordering for $D_x$, we recursively apply the following procedure. Let $D_x$ be composed of a set of subgraphs $D_1,\dots , D_k$, forming a parallel or a series composition. If $D_1,\dots , D_k$ form a parallel composition, then either $k=2$, or $k=3$ and $D_3$ is a single edge; otherwise, the graph violates Condition (S.1). If we remove the sink and source from G, then, by Condition (S.2), we have a good st-ordering if and only if all nodes of $D_1$ precede all nodes of $D_2$, there is exactly one sink in $D_1$, and there is exactly one source in $D_2$. If $D_1,\dots , D_k$ form a series composition, we construct good st-orderings of $D_1,\dots , D_k$ recursively and merge them in a good st-ordering of $D_x$.    $\square$

5 Open Problems

We introduced rectilinear greedy drawings, i.e., planar greedy drawings in the orthogonal drawing style with no bends. Our work reveals several interesting open problems. (1) What if we allow bends along the edges? (2) Can we always test in polynomial time whether a planar DAG admits a good st-ordering? (3) Given a biconnected plane graph G, what is the complexity of deciding whether G admits a (universal) greedy rectilinear representation? This question pertains the intermediate step of the topology-shape-metrics approach [23].