A Walk on the Wild Side: A Shape-First Methodology for Orthogonal Drawings

Orthogonal drawings, where edges are represented as chains of horizontal and vertical segments, are a foundational topic in Graph Drawing, valued both for their practical applications and for the rich body of research they have inspired over the past four decades.

The most well-known and widely studied methodology for constructing orthogonal drawings is the Topology-Shape-Metrics (TSM) approach (see, e.g., [19, 42, 43]). TSM generates an orthogonal drawing in three steps. First, a planar embedding (topology) of the graph is computed, and dummy vertices are possibly introduced to represent edge crossings. Second, a shape – minimizing the number of bends (points where two edge segments meet at a right angle) – is computed, see [40]. Third, an orthogonal drawing (metrics) consistent with the computed shape is constructed. Although originally designed for graphs with maximum degree $4$, TSM has been extended to general graphs by either representing vertices as boxes sized proportionally to their degree (see, e.g., [4, 5]), or by allowing partial edge overlaps, which requires adapting the flow-based optimization accordingly (see, e.g., [22, 24]).

While TSM is arguably the most well-known method, alternative approaches have been proposed for orthogonal drawings (see, e.g., [10, 11, 33, 34, 39]). Nonetheless, the comprehensive and still influential quantitative aggregate [3] evaluation in [20] shows that the TSM approach outperforms all the above cited alternative methods across nearly all standard graph drawing metrics. Note that other algorithms (see e.g., [28]) have been proposed and assessed not through quantitative measures but via user studies. Also, the algorithm in [26] neglects the experiments in [20] in favor of a comparison with [28].

Furthermore, the success of TSM is underscored by its implementation in widely used open-source libraries such as ogdf [13] and GDToolkit [18], as well as its adoption in the Graph Drawing engine of yWorks [22, 24, 29, 36], a leading company in graph visualization.

However, two key observations can be made. (1) Existing algorithms, including those based on TSM, prioritize minimizing crossings. This often leads to unnecessarily long edge paths with many bends and results in drawings with large area and poor geometric uniformity. (2) Several studies (e.g., [27]) have shown that orthogonal crossings, where edges meet at right angles, have minimal impact on readability. This suggests that aggressively minimizing crossings in orthogonal drawings may not always be the optimal design goal.

In this paper, we start from the two aforementioned observations and introduce a methodology, called Shape-Metrics (SM), that “subverts” the traditional TSM pipeline. SM focuses first on bends. Namely, given a graph $G$, we ideally seek to construct a rectilinear drawing of $G$, that is, a drawing in which all edges are represented by straight horizontal or vertical segments with no bends. When such a drawing is not feasible, we incrementally subdivide the edges of $G$ by introducing dummy vertices. Each of these vertices will (possibly) correspond to a bend in the final drawing. We continue this process until we obtain a subdivision of $G$ that admits a rectilinear drawing. Once such a subdivision is found, the final metric phase computes the actual coordinates of the drawing.

SM is based on the concept of shaped graph, which we define as an assignment of a label from the set $ℒ=\{L,R,D,U\}$ to each of its edges, indicating the direction – Left, Right, Down, or Up – of that edge in a drawing. Given a shaped graph, it can be decided in polynomial time [30] if it admits a rectilinear drawing with that shape. On the other hand, checking if a graph admits a rectilinear drawable shape is NP-complete [21]. We exploit a new simple characterization of rectilinear drawable shaped graphs. Informally, a shaped cycle is said to be complete if its edges have all the four labels; we show that a shaped graph is rectilinear drawable if and only if all its cycles are complete.

We tackle the NP-hardness barrier by formulating the rectilinear drawability testing problem as a Boolean satisfiability (SAT) problem and leveraging the power of modern SAT solvers. SAT solvers have already proven to be effective in combinatorics and geometry (see, e.g., [12, 17, 31, 37, 38]). However, as far as we know, SAT solvers have rarely been applied to Graph Drawing. The related works we are aware of are [9], which employs a hybrid ILP/SAT approach to compute $st$-orientations and visibility representations, [8] where a SAT solver is used to compute book embeddings, and [14, 15, 16] where a SAT solver is used to test upward planarity.

There are differences and analogies between SM and TSM. TSM leverages the fact that checking if a graph is planar can be done efficiently. On our side we have that, unfortunately, checking if a graph is rectilinear drawable is NP-complete [21]. On the other hand both methodologies use specific properties of shapes: TSM’s cornerstone is the balance of turns in shapes of faces of planar graphs [44], while SM’s cornerstone is the completeness of cycles. Also, both methodologies augment the graph to be drawn with dummy vertices, TSM to represent crossings, SM to represent bends.

We implemented SM in a tool called domus (Drawing Orthogonal Metrics Using the Shape) and experimented its effectiveness against the TSM implementation available in ogdf [13] measuring widely adopted Graph Drawing metrics [3, 20]. Although other comparable tools exist (e.g., GDToolkit [18]), we selected ogdf as our benchmark due to its open-source nature, widespread adoption within the Graph Drawing community, and the fact that it has benefited from over a decade of active development and optimization. In view of the results in [20] it was pointless to compare domus with the algorithms in [10, 11, 33, 34, 39]. Also, the algorithms in [26, 28] adopt a definition of orthogonal drawing which is different from the widely adopted one given in this paper. E.g., even if a vertex has degree less or equal than $4$ more than one of its incident edges can exit from the same direction. Hence, comparing domus with them would be unfair.

We did two sets of experiments, which we refer to as “in-vitro” and “in-the-wild”. The in-vitro experiments aim to thoroughly evaluate the performance and characteristics of SM, including the use of the SAT solver, on a dataset of random graphs with predefined sizes and densities. These graphs have a maximum degree of $4$, which is the baseline for orthogonal drawings, and contain $20-60$ vertices, a range considered important for node-link representations in graph visualization (see, e.g., [25]). The in-the-wild experiments use the Rome Graphs dataset [20], which is one of the most popular collections of graphs [3], comprised of $11,534$ graphs, having $10-100$ vertices and $9-158$ edges, with maximum degree $13$. The experiments show that for most of the typical graph drawing metrics [3], domus outperforms the TSM algorithm implemented in ogdf. Moreover, SM is simple to implement: it reduces shape constraints to a SAT formula, invokes an off-the-shelf SAT solver, and computes the final drawing metrics using a slight variation of standard TSM compaction techniques. Figure 1 shows two drawings of the same graph, one produced with ogdf and the other with domus.

The paper is organized as follows. Preliminaries are in Section 2. Section 3 illustrates the characterization of rectilinear drawable shaped graphs which is the milestone of SM. Section 4 describes SM, clarifying how its steps are activated and implemented and the role played by the SAT-solver. Section 5 and Section 6 show the in-vitro and the in-the-wild experiments, respectively. Conclusions and open problems are proposed in Section 7. Because of space limitations some proofs are only sketched. A full version of such proofs and other extra material is in [1].

For basic graph drawing terminology and definitions refer, e.g., to [19, 32].

Let $G$ be a graph. with vertex set $V(G)$ and edge set $E(G)$. For technical reasons, we assign an arbitrary (e.g., random) orientation to each edge in $E(G)$; thus, if an edge is denoted as $(u,v)$, it is considered as directed from $u$ to $v$. However, when referring to paths, cycles, vertex degrees, or connectivity in $G$, we disregard these orientations. A path (resp., cycle) of $G$ is simple if each of its vertices occurs only once.

A cut-vertex is a vertex whose removal disconnects $G$. Graph $G$ is biconnected if it has no cut-vertex. A biconnected component of $G$ is a maximal (in terms of vertices and edges) biconnected subgraph of $G$. A biconnected component is trivial if it consists of a single edge and non-trivial otherwise. Unless otherwise specified we assume that graphs are connected.

In a rectilinear drawing of $G$: (i) Each vertex $v\in V(G)$ is represented by a point with integer coordinates, denoted by $x(v)$ and $y(v)$. (ii) No two vertices are represented by the same point. (iii) Each edge is represented by either a horizontal or a vertical line segment connecting the points that represent its end-vertices. (iv) The interior of a segment representing an edge does not intersect any point representing a vertex. A graph is said to be rectilinear drawable if it admits a rectilinear drawing. Note that such a drawing requires each vertex to have degree at most $4$. Hence, unless otherwise specified, we will consider graphs with maximum vertex degree $4$.

We use the label set $ℒ=\{L,R,D,U\}$ to denote directions, where $L$, $R$, $D$, and $U$ stand for left, right, down, and up, respectively. Also, we say that $L$ and $R$ are opposite labels, and likewise, $D$ and $U$ are opposite labels. For any label $A\in ℒ$, we denote its opposite by $\overline{A}$.

A shape of a graph $G$ is a function $\lambda$ that assigns to each edge $(u,v)\in E(G)$ a label from the set $ℒ$. Consider an edge $(u,v)$. Labeling $(u,v)$ with, say, $R$ indicates that in the shape of $G$, the edge is directed to the right when traversed from $u$ to $v$. Clearly, if the edge is traversed in the opposite direction (from $v$ to $u$) the direction should be left. Hence, with a little abuse of notation, if $\lambda (u,v)=R$ (resp. $\lambda (u,v)=L$) we say that $\lambda (v,u)=L$ (resp. $\lambda (v,u)=R$). The other labels are treated analogously. Additionally, for each pair of edges that share a vertex $v$ it is mandatory that $\lambda (v,u)\ne \lambda (v,w)$. This constraint ensures that two edges sharing the same vertex “cannot point in the same direction”, preventing the two edges from “overlapping”. We define a shaped graph to be a graph with a shape.

A shape can be assigned to a graph by starting from one of its rectilinear drawings, if such a drawing exists. Namely, given a rectilinear drawing $\mathrm{\Gamma }$ of a graph $G$ we can label the edges $E(G)$ as follows. For each $(u,v)\in E(G)$: (i) If we set $\lambda (u,v)=R$, (ii) If $x(u)>x(v)$ we set $\lambda (u,v)=L$, (iii) If we set $\lambda (u,v)=U$, (iv) If $y(u)>y(v)$ we set $\lambda (u,v)=D$. We say that this is the shape of $\mathrm{\Gamma }$. It is easy to check that this labeling is consistent with the definition of shape, and hence it is also a valid shape for $G$.

A shaped graph is rectilinear drawable if it admits a rectilinear drawing having exactly its shape. The shaped graph in Figure 2(a) is not rectilinear drawable. Figure 2(d) shows a failed attempt to construct a rectilinear drawing of such a shaped graph.

Given a graph $G$ a subdivision of $G$ is a graph $G^{\prime }$ obtained by replacing certain edges of $E(G)$ with internally vertex-disjoint simple paths. The new vertices in $V(G^{\prime })\setminus V(G)$ introduced along these paths are called dummy vertices. An orthogonal drawing $\mathrm{\Gamma }$ of $G$ is a rectilinear drawing of a subdivision of $G$. Let $v$ be a dummy vertex, if the two segments incident to $v$ in $\mathrm{\Gamma }$ are one horizontal and one vertical, then $v$ is called a bend.

The methodology we present in Section 4 is based on the results presented in this section.

Consider a shaped simple cycle $c=v_0,v_1,\mathrm{\dots },v_{p-1}$, with $p\ge 4$, of $G$. We say that $c$ is complete if it contains four pairs of vertices $v_i,v_{i+1}$, $v_j,v_{j+1}$, $v_h,v_{h+1}$, and $v_k,v_{k+1}$ such that: (i) $\lambda (v_i,v_{i+1})=L$, (ii) $\lambda (v_j,v_{j+1})=R$, (iii) $\lambda (v_h,v_{h+1})=D$, (iv) $\lambda (v_k,v_{k+1})=U$, where the vertices indexes of $c$ are intended $\text{mod }p$. An example of a complete cycle is shown in Figure 2(b), while Figure 2(c) illustrates a cycle that is not complete.

This section presents SM. Given an $n$-vertex graph $G$ as input, it produces an orthogonal drawing $\mathrm{\Gamma }$ of $G$ as output. SM consists of two steps, called Shape Construction and Drawing Construction, see Figure 4. Each of these steps can be repeated multiple times.

We implemented SM in our tool domus and evaluate its effectiveness through comprehensive “in vitro” experiments conducted using domus. Specifically, we describe: (i) the implementation choices in domus that define some aspects of SM, (ii) the benchmark adversary for comparison, (iii) the graph dataset and its key characteristics, (iv) the computational platform used, (v) the evaluation metrics, (vi) the experimental results for each metric, and (vii) internal performance indicators, such as SAT solver invocations per graph.

Two drawings of a graph in the dataset are in Figure 5.

(i) In domus, we made specific implementation choices regarding the SAT solver, the initial cycle set $𝒞$, coordinate computation, and randomization. For the SAT solver, we chose Glucose [2] because it is open source and it is well known for its efficiency. Importantly, Glucose provides proofs of unsatisfiability, which we use to identify edges to split, thereby increasing flexibility in the drawing. To initialize the cycle set $𝒞$, domus computes a cycle basis covering all edges in the non-trivial biconnected components of the input graph $G$. This is done via a BFS from an arbitrary root to construct a tree $T$; for each non-tree edge $(u,v)$, we add the cycle formed by $(u,v)$ and the unique paths from $u$ and $v$ to their lowest common ancestor in $T$. This results in an initial set of size $|𝒞|=|E(G)|-|V(G)|+1$. For coordinate assignment, after computing $G_x$ and $G_y$, domus uses a compaction algorithm similar to that in ogdf. For details on compaction algorithms see, e.g., [6, 7, 29, 35]. Finally, Glucose can make random choices. In order to enforce replicability of the experiments we forced it to work deterministically.
(ii) For the motivations discussed in Section 1, we compared the performance of domus against the TSM implementation available in ogdf [13]. Another option was to use as a benchmark one of the tools (see, e.g. [28]) that have been evaluated via user studies. However, this comparison would be useless, since most of this tools adopt a definition of orthogonal drawing which is different from the widely adopted one given in Section 2. E.g., even if a vertex has degree less or equal than $4$ more than one of its incident edges can exit from the same direction. Also, vertices and bends neither have integer coordinates nor it is easy to “snap” them to a grid (see [1] for a comparison with these models).
(iii) We generated $4,100$ connected graphs uniformly at random, each with maximum vertex degree $4$. Their sizes range from $20$ to $60$ vertices, and their densities – defined as the ratio between the number of edges to the number of vertices – span $1.25$ to $1.75$ in steps of 0.005. For degree $4$ graphs, the theoretical maximum density is $2$. Namely, for each $n=20,\mathrm{\dots },60$ and $i=1,2,\mathrm{\dots },100$ we generated a graph $G_{n,i}$ with density $d_i=1.25+i\cdot (1.75-1.25)/100$. Hence, for each value of $n$ the graphs have roughly $100$ possible densities ranging from $1.25$ to $1.75$, in increments of 0.005. In terms of number of edges we have $|E(G_{n,i})|=\lfloor n\cdot d_i\rfloor$. For instance, the graph $G_{20,50}$ has $30$ edges, while $G_{60,100}$ has $105$ edges. For each $n$ and $d_i$ we initialized a graph with $n$ vertices and no edges. Then, we repeatedly randomized two vertices $u$ and $v$ of the graph and added an edge between them, until $d_i$ was reached. If $u=v$ or if $(u,v)$ was already in the graph, or if either $u$ or $v$ was already degree $4$, we skipped the pair. Finally, the instance was rejected if non-connected.

Conducting experiments on a set of randomly generated graphs was a necessary choice, as, to the best of our knowledge, no publicly available collection of maximum-degree-4 graphs is currently recognized as a standard benchmark for graph drawing experiments.
(iv) All the experiments were performed running ogdf and domus on a personal computer with a 3.15 GHz Intel processor (comparable with an M1 Apple processor).

(v) Following the framework proposed in [20], we compared the drawings produced by domus and those generated by ogdf using the following metrics: the total number of Bends in the drawing; the total number of edge Crossings; the standard deviation of the number of bends per edge (Bends Deviation); the maximum number of bends on any single edge (Max Bends); the Area occupied by the drawing; the sum of the length of all the edges (Total Edge Length); the length of the longest edge (Max Edge Length); the standard deviation of edge lengths (Edge Length Deviation) and the total computation Time to build the drawing, measured in seconds. Using the terminology in [3], we adopt most of the metrics suggested for “quantitative individual” and “aggregated” evaluations. A note on how the above metrics were computed is in [1].

(vi) The results of our experiments are shown in Figures 6 and 7, where each random graph is represented by a small circle. The $x$-coordinate corresponds to the metric value produced by ogdf, while the $y$-coordinate reflects the value obtained by domus. Points below the bisector of the first quadrant (gray dashed line) indicate cases where domus outperformed ogdf; points above indicate the opposite. To account for overlapping data points (caused by graphs with same metric values), each plot includes a red dashed trend line summarizing the comparative performance. We also report the coefficient of determination ($R^2$, with $0\le R^2\le 1$), with values closer to $1$ indicating a better interpolation.

Figure 6(a) focuses on Bends. domus outperformed ogdf on $78\%$ of the graphs and matched its performance on another $7\%$. The trend line indicates a modest quadratic improvement, a linear improvement of approximately $2\%$, and a constant improvement of about $2.5$ bends per graph. Notably, $89$ of the random graphs admit a rectilinear drawing. Conversely, as expected (Figure 6(b)), ogdf sharply outperforms domus in terms of Crossings. In this case, $149$ random graphs admit a planar drawing. Additional insights regarding bends are in Figures 6(c) and 6(d), which report the Bends Deviation and the Max Bends per edge, respectively. For the former metric, domus outperforms ogdf on $85\%$ of the graphs. For the latter, domus matches ogdf on $50\%$ of the graphs and outperforms it in the remaining $50\%$. Since the possible values of the maximum number of bends per edge are relatively few, many graphs correspond to the same point. Because of this, in Figure 6(d) we represent with a variable size circle the number of graphs having the maximum number of bends per edge. The area of each circle is proportional to the corresponding number of graphs. These results indicate that our approach not only reduces the total number of bends but also achieves a more uniform distribution of bends across edges, thereby avoiding drawings with edges that contain long sequences of consecutive bends.

domus yields more compact drawings compared to those generated by ogdf (Figure 7(a)). Specifically, our approach results in smaller drawing areas for $78\%$ of the graphs, and matches ogdf in $18\%$ of the cases. The trend line indicates a consistent improvement, with an average area reduction of approximately $25\%$. We also achieve slightly better results than ogdf in terms of edge length. domus produces drawings with lower Total Edge Length for $50\%$ of the graphs and matches ogdf on $1\%$ of them (Figure 7(b)). More significantly, domus outperforms ogdf on Max Edge Length (Figure 7(c)) for $87\%$ of the graphs and obtain equal results for an additional $10\%$. Similarly, for Edge Length Deviation (Figure 7(d)), domus performs better on $89\%$ of the graphs. These results indicate that SM not only tends to produce slightly shorter edges overall but also ensures a more uniform edge length distribution, thereby avoiding disproportionately long edges that can hinder readability and spatial coherence.

Figure 8 illustrates how the relative performance of domus and ogdf varies with the number of vertices and the density of the input graphs. In each subfigure, a circle positioned at coordinates $(x,y)$ represents all graphs with $x$ vertices and density $y$. For a given metric $M$ and each pair $(x,y)$, let $M_O$ (respectively, $M_D$) denote the average value of $M$ for the drawings produced by ogdf (respectively, domus) over all graphs with $x$ vertices and density $y$. The circle at $(x,y)$ is colored red, blue, or gray if , $M_O>M_D$, or $M_O=M_D$, respectively. Figure 8(a) shows that for small values of $n$, increasing graph density tends to favor ogdf. However, this advantage gradually diminishes as $n$ increases. For the Area, we have a similar trend. The other metrics do not show any clear dependency on either the number of vertices or the density (Figures 8(b), 8(c), and 8(d)). [1] contains additional diagrams about the density.

(vii) To further characterize the computations performed by domus, for each run on a single graph, we measured the following (see Figure 9).

First, we measured how many cycles were added to $𝒞$ during the computation. Each addition corresponds to a case where the current shape was found to be non-rectilinear drawable, triggering a new invocation of Shape Construction from Drawing Construction. In each of such invocations, the SAT solver was able to quickly find a satisfying assignment. The total number of Drawing Construction calls equals this number plus one. Figure 9(a) shows a cumulative distribution function (CDF) of these data. For instance, in 80% of the graphs, no more than 100 cycles were added to $𝒞$.

Second, we measured the number of dummy vertices introduced by the Shape Construction, corresponding to how often the Shape Construction called itself due to the absence of a shape satisfying the constraints. In each of these invocations, the formula given to the SAT solver was unsatisfiable. Figure 9(b) shows that at most $25$ dummy vertices have been added for $80\%$ of graphs. Such vertices do not necessarily become bends in the final drawing, since some of them can get an angle of $\pi$ between their incident edges. So, a dummy vertex that does not become a bend can be viewed as a failure in the attempt to decrease the constraints of the drawing. Hence, we also computed how many dummy vertices actually became bends in the final drawing. This is an indirect measure of the effectiveness of using SAT unsatisfiability proofs to introduce bends. Figure 9(b) shows that almost all the dummy vertices became bends in the drawing.

Third, we measured the total number of SAT solver invocations, computed as the sum of the Shape Construction self-invocations, the Shape Construction calls by the Drawing Construction, plus one. Figure 9(c) shows that at most $120$ SAT invocations have been done for $80\%$ of graphs. The similarity between Figure 9(a) and Figure 9(c) shows that most of the SAT solver calls ($80\%$) depend on the need to add a cycle to $𝒞$. Also, the average number of Boolean variables and clauses in the input to the SAT solver were $352$ and $1224$, respectively.

Fourth, Figure 9(d) shows that computing a drawing for domus required at most $10$ seconds for $80\%$ of graphs and that there are graphs that required more than $100$ seconds, with an average latency of $70$ seconds. ogdf did its work in an average of $0.06$ seconds.

With small modifications, it is possible to apply our methodology to construct orthogonal drawings of graphs with degree greater than $4$. In representing such graphs, we use the same convention introduced in [24]. Namely, the edges exiting the same side of a vertex can partially overlap (they are distanced by a very small amount) only for the first segment representing them. See Figure 10. The variation of the methodology works as follows. First, we modify the ${ℱ}_{G,𝒞}$ formula in such a way that if a vertex $v$ has degree greater than $4$ more than one edge can enter $v$ from the same direction, while keeping the constraint that at least one edge enters $v$ from all the directions. After that, all the machinery that looks for a shape, including the usage of the SAT solver, stays the same. Second, once a shape has been found, $v$ is temporarily expanded into a box (which will not be shown in the drawing) and the edges incident to the same side of $v$ are separated by introducing inside the box dummy vertices that become bends in the final drawing. After that, a metric is computed with the same technique as before. See drawings of Rome graphs in Figure 10.

We compared ogdf and domus in experiments that we call “in the wild” using the Rome Graphs dataset [20], which was originated by real-life applications and whose vertices have no degree restriction (see Figures 11 and 12). The experiments further increase the advantage of domus with respect to ogdf (see Section 5) in terms of Bends (Figures 11(a), 11(c), and 11(d)) and confirm that ogdf performs much better in terms of Crossings (Figure 11(b)). This probably depends on the low densities of the Rome Graphs, which are close to planar in terms of graph edit distance. Further, domus performs better than ogdf in terms of Area, Max Edge Length, and Edge Length Deviation (Figures 12(a), 12(c), and 12(d)) and the two tools are comparable for Total Edge Length (Figure 12(b)). Hence, the presence of vertices of degree greater than $4$ does not change too much the experimental results. ogdf was, even in this case, much faster than domus, since the average duration of its computations was $0.07$ seconds with a maximum of $3.3$ seconds. The domus computations took an average of $1.44$ seconds, with a maximum of $769$ seconds.

About forty years after the introduction of the Topology-Shape-Metrics (TSM) approach for orthogonal drawings, we propose a novel methodology that subverts the TSM pipeline by prioritizing bend minimization over crossing minimization. Our experimental results demonstrate that this shift yields improvements across most standard metrics used in Graph Drawing to evaluate the effectiveness of a layout algorithm.

As a final remark, we observe that our methodology can be exploited to construct drawings incorporating several types of constraints (for an introduction to constrained orthogonal drawings, see, e.g., [23, 41]). If the graph contains edges that should be drawn upward it is easy to impose this by setting the value true for the corresponding $u$-variables of the ${ℱ}_{G,𝒞}$ formula. Similarly, giving the appropriate true-false values to the corresponding $\mathrm{\ell }$-, $r$-, $d$-, and $u$-variables it is possible to specify that certain edges should enter their end-vertices respecting some specific orientations (so called side-constraints). Further, it is easy to specify that a given edge should be horizontal or vertical or to impose the shape of entire sub-graphs.

We open several promising research directions, including the following:

• $\mathrm{■}$

  Does there exist, at least for some families of graphs, a “small” set of cycles whose completeness implies the completeness of all cycles in $G$? If so, can such a set be efficiently computed? In [1] it is shown that this problem is not trivial.

• $\mathrm{■}$

  Our methodology entirely disregards crossings. Is it possible to modify the approach to incorporate constraints that upper-bound the number of crossings?

• $\mathrm{■}$

  TSM and our methodology can be viewed as two extremes of a broader design space for constructing orthogonal drawings. Can hybrid methods be developed that combine elements of both approaches?

• $\mathrm{■}$

  In this paper, we employed compaction techniques originally developed within the TSM paradigm. It would be interesting to design compaction methods that do not work on the planarized underlying graph, but that only preserve the shape of the edges.

• $\mathrm{■}$

  Our approach can be leveraged to compute a maximal rectilinear drawable subgraph by iteratively invoking a SAT solver. Can the methodology be redesigned or optimized for greater efficiency when solving this specific problem?

For the sake of reproducibility all our software and our data sets are publicly available at https://github.com/shape-metrics/domus.