Planar Stories of Graph Drawings: Algorithms and Experiments

In this paper we address the second type of strategy mentioned above. We introduce a new model for the dynamic visualization of a static graph as a sequence of frames. This model assumes that the input is a geometric graph $G$ (i.e., a graph drawn in the plane with straight-line edges, for example by some force-directed algorithm) and aims to generate a sequence of visualization frames such that: $(i)$ the vertices of $G$ are all present in any frame, always at their initial input coordinates; $(ii)$ the initial frame contains a subset of edges that yields a planar subgraph; $(iii)$ in each subsequent frame, exactly one new edge $e$ enters the visualization and the minimum subset of edges of the current frame that together with $e$ violate planarity disappear; $(iv)$ when an edge leaves the visualization, it no longer appears in the future; $(v)$ the union of all frames contains the whole edge set of $G$. We call such a sequence of frames a planar story of $G$ (see Section 3 for a formal definition).

A natural objective function when computing a planar story is that the amount of edges in any frame is not too small. More precisely, we are interested in planar stories whose minimum number of edges contemporarily displayed (across the entire sequence of frames) is maximized. We call such a story min-frame optimal. Besides studying our model from a theoretical point of view, we design and experimentally compare different algorithms (both exact techniques and heuristics). Our main results are as follows:

• $\mathrm{■}$

  We show in Section 5 that a min-frame optimal planar story of a geometric graph $G$ can be efficiently computed when $G$ is 2-plane (i.e., each edge is crossed at most twice), although the problem is NP-hard in the general case (Section 4).

• $\mathrm{■}$

  We describe several heuristics based on a common greedy framework; all of them work for general graphs (Section 5). They differ in the strategy for computing the initial and the last frames, and in the criteria used to select the edge that enters the visualization in each subsequent frame. We also describe an Integer Linear Program (ILP) that solves the problem optimally (Section 6).

• $\mathrm{■}$

  We discuss the results of an extensive experimental analysis that compares our heuristics and the exact algorithm. The results highlight algorithmic trade-offs between efficiency and effectiveness, and show how some of our heuristics are able to achieve the optimum in many cases in a short runtime. See Section 7.

The paper concludes by discussing some future research directions (Section 8). Due to space limitations some proofs and technical details can be found in [5].

Let $e$ be an edge in $F_1$. By Remark 1, $e$ is crossed by some edge $e^{\prime }$ of the graph. Let $F_i$ be the first frame of $\sigma$ that contains $e^{\prime }$, with $i\ge 2$. By definition of planar story, $e$ does not occur in any frame $F_j$ with $j\ge i$. In particular, $e$ is not contained in $F_{\tau }$. $◀$

Given a planar frame $F$ of $G$, let ${\mu }_F(G)$ be the maximum $\mu (\sigma )$ over all planar stories $\sigma$ of $G$ with initial frame $F$. Proposition 2 implies the following.

The crossing graph $X$ of a geometric graph $G$ is defined as follows: $(i)$ the vertex set $V(X)$ corresponds to the edge set $E(G)$; $(ii)$ there is an edge $uv\in E(X)$ if and only if the edges corresponding to $u$ and $v$ in $E(G)$ cross each other. The crossing-free edges of $G$ correspond to isolated vertices of $X$; by Remark 1, we assume that $X$ has no isolated vertices. Note that a graph is the crossing graph of a geometric graph if and only if it is a segment intersection graph [29]. This includes cliques, but also planar graphs [10, 19]. The crossing graph of a geometric graph with $m$ edges and $\chi$ crossings can be computed in $𝒪(m\log m+\chi )$ time with the algorithm of Balaban [3] for segment intersection.

If $\sigma =⟨F_1,\mathrm{\dots },F_{\tau }⟩$ is a planar story of $G$, each frame $F_i$ ($i\in \{1,\mathrm{\dots },\tau \}$) corresponds to an independent set $X[F_i]$ of $X$, i.e., no two vertices of $X[F_i]$ are adjacent. We denote by ${\sigma }_X=⟨X[F_1],\mathrm{\dots },X[F_{\tau }]⟩$ the sequence that describes the planar story $\sigma$ from the point of view of $X$. See Fig.˜2 for an example. We will also refer to ${\sigma }_X$ as a planar story and to the independent sets $X[F_i]$ as (planar) frames. If not stated otherwise, we use red for the initial frame and blue for the final frame in our figures. A maximum pair of independent sets is a pair $(I_1,I_2)$ of two disjoint independent sets such that $\min \{|I_1|,|I_2|\}$ is maximum. A maximum pair $(I_1,I_2)$ of independent sets is Pareto optimal if also $\max \{|I_1|,|I_2|\}$ is maximum. As a further corollary of Proposition 2, we obtain the following.

We observe that, in order to get a min-frame optimal story of a geometric graph $G$, it might be necessary to choose as the initial frame a planar subgraph of $G$ that is not a maximal planar subgraph. In terms of the crossing graph, this means that it might be necessary to start with an independent set that is not maximal. See Fig.˜3 for an example where the crossing graph is a caterpillar.

It is easy to see that MaxMinFramePlanarStoryD($G$,$m$) is in NP. To prove the hardness, we apply a reduction from PlanarMaximumIndependentSetD($H$,$k$), i.e., the problem of deciding whether a planar graph $H$ admits an independent set of size at least $k$; this problem is known to be NP-hard [30, Theorem 4.1]. To this end, let $X$ be the disjoint union of $H$ and a star $S$ with $k+1$ leaves (see Fig.˜4). Since $X$ is planar, it is a segment intersection graph [10], i.e., a crossing graph of some geometric graph $G$. We show that $\mu (G)\ge k+1=:m$ if and only if $H$ contains an independent set of size at least $k$.

Assume first that $H$ contains an independent set $I$ of size at least $k$. Consider the following planar story. The initial frame contains the edges corresponding to $I$ and the center of the star $S$. The size of the initial frame is $k+1$. For the subsequent frames, we add the edges corresponding to the leaves of $S$, in any arbitrary order. This increases the size of the frame up to $2k+1$. Finally, we add in arbitrary order all edges corresponding to vertices of $H$ that were not in $I$. During this process, the edges corresponding to the leaves of $S$ will never be removed. Thus, the size of each frame is at least $k+1$.

Assume now that there is a planar story $\sigma$ of $G$ with $\mu (\sigma )\ge k+1$. We show that $H$ contains an independent set of size at least $k$. Let $F$ be the frame of $\sigma$ that contains the edge corresponding to the center of $S$. In this frame, there is no edge corresponding to a leaf of $S$. This implies that frame $F$ must contain at least $k$ non-intersecting edges that correspond to at least $k$ independent vertices of $H$. $◀$

We propose three alternative strategies for computing the initial frame $F_1$ and the last frame $F_{\tau }$, or in other words two possibly large disjoint independent sets $I_1$ (initial frame) and $I_{\tau }$ (final frame) of the crossing graph $X$ of $G$.

1a.

$(I_1,I_{\tau })$ is a Pareto optimal maximum pair of independent sets such that $|I_1|\le |I_{\tau }|$. See Thm.˜6 for the computation.

1b.

$I_1$ is a large independent set of $X$ of size at most $|E(G)|/2$ and $I_{\tau }$ is a maximal independent set of $X-I_1$. More precisely, we use the following approach: While $|I_1|\le |E(G)|/2-1$ and $X-I_1-N(I_1)$ is not empty, iteratively add a vertex of minimum degree in $X-I_1-N(I_1)$ to $I_1$. Then, iteratively add a vertex of minimum degree in $X-I_1-I_{\tau }-N(I_{\tau })$ to $I_{\tau }$.

1c.

Alternating between $i=1$ and $i=\tau$, iteratively add a vertex of minimum degree in $X-I_1-I_{\tau }-N(I_i)$ (if there exists one) to $I_i$. If $|I_1|>|I_{\tau }|$, exchange $I_1$ and $I_{\tau }$.

Variants 1b and 1c can be implemented in linear time in the size of $X$ by sorting the vertices in buckets according to their degrees. Regarding Variant 1a, while it is NP-hard to find a maximum pair of independent sets in a graph [5], there exists a fixed-parameter tractable (FPT) algorithm parameterized by the treewidth of the graph (Thm.˜6). Therefore, Variant 1a can be much slower than Variants 1b and 1c, although it may lead to better solutions. We also remark that Thm.˜6 establishes a result of independent interest, which goes beyond the purposes of our specific problem.

A tree decomposition [39] of a graph $X$ is a tree $𝒯$ such that each vertex $\nu \in V(𝒯)$ is associated with a set $V(\nu )\subseteq V(X)$, called the bag of $\nu$, such that

1. (a)

   ${\bigcup }_{\nu \in V(𝒯)}V(\nu )=V(X)$,

2. (b)

   for each edge $uv\in E(X)$, there is a vertex $\nu \in V(𝒯)$ such that $u,v\in V(\nu )$, and,

3. (c)

   for each $v\in V(X)$, the subgraph of $𝒯$ induced by the vertices $\{\nu \in V(𝒯)|v\in V(\nu )\}$ is connected.

The width of a tree decomposition is ${\max }_{\nu \in V(𝒯)}|V(\nu )|-1$. The treewidth tw$(X)$ of a graph $X$ is the minimum among the widths of any of its tree decompositions.

The proof follows the ideas of the FPT approach for constructing a minimum vertex cover as proposed by Niedermeier [33], enhancing it with the concept of Pareto optimal pairs. Root $𝒯$ at an arbitrary vertex. We use dynamic programming. For a vertex $\nu$ of $𝒯$ let $X(\nu )$ be the subgraph of $X$ induced by the vertices in the bags of the subtree of $𝒯$ rooted at $\nu$. For each map $c:V(\nu )\to \{$red, blue, white$\}$, we compute the list $L(\nu ,c)$ of Pareto-optimal pairs $(\alpha ,\beta )$ for which $X(\nu )$ contains two disjoint independent sets $I_1$ and $I_2$ of size $\alpha$ and $\beta$, respectively, such that the red vertices of $V(\nu )$ are contained in $I_1$, the blue vertices of $V(\nu )$ in $I_2$, and the white vertices of $V(\nu )$ are neither in $I_1$ nor $I_2$. $◀$

Given a Pareto-optimal maximum pair $(I_1,I_{\tau })$ of independent sets, Advanced Greedy 1a does not necessarily result in a planar story with minimum frame size among all planar stories with initial frame $I_1$ and final frame $I_{\tau }$. An example is given in Fig.˜6: here, there is a vertex that is neither in the initial nor in the final frame whose degree is greater than 3.

The frame sizes are first monotonically increasing and then monotonically decreasing and, thus, at least $\min \{|I_1|,|I_{\tau }|\}$, which, by Corollary 4, is optimum. $◀$

The statement for 3-plane graphs is a corollary of Lemma 7. For 2-plane graphs, the crossing graph has maximum degree two and, thus, its connected components are paths and cycles, and a maximum pair $(I_1,I_{\tau })$ of independent sets can be computed in linear time. See Fig.˜7. Moreover, if we apply Advanced Greedy 1a then the minimum frame size is $\min \{|I_1|,|I_{\tau }|\}$, unless there is an even cycle but no odd path. In this case, the minimum frame size is $\min \{|I_1|,|I_{\tau }|\}-1$. $◀$

In each step of Phase 2, the set $E^{\prime }$ of admissible future edges with minimum current degree might contain multiple edges. For an edge $e\in E^{\prime }$, denote by $C(e)$ the set of current edges that cross $e$. Also, let $E^{\prime \prime }\subseteq E^{\prime }$ be the subset of edges in $E^{\prime }$ such that, for any $e\in E^{\prime \prime }$, the number of future edges crossing some edges in $C(e)$ is the maximum over all other edges in $E^{\prime }$. We consider two alternative strategies for selecting the next future edge $e$ that enters the drawing: 2a. $e$ is chosen uniformly at random in $E^{\prime }$; or 2b. $e$ is chosen uniformly at random in $E^{\prime \prime }$.

Variant 2b applies a tie-breaking rule to further restrict the set of admissible edges that can be selected. The rationale is to maximize the amount of future edges that will benefit from the removal of the current neighbors of the edge that will enter the drawing.

To evaluate the performance of our algorithms on different types of graphs, we used several test suites, totaling $637$ instances¹¹1To allow replicability, we made the whole graph benchmark publicly available at https://github.com/ekatsanou/edge-based-graph-stories.. We considered two main types of instances: Geometric Graphs and Crossing Graphs.

A collection of both random and real graphs drawn with a force-directed algorithm. The different graph classes are as follows

• $\mathrm{■}$

  random graphs: $200$ geometric graphs: For each $n\in \{10,20,\mathrm{\dots },100\}$ and for each density²²2The density of a graph is the number of its edges divided by the number of its vertices. $d\in \{1.2,1.6,2.0,2.4\}$, we randomly generated $5$ distinct graphs with $n$ vertices and $m=d\cdot n$ edges, with Erdős–Rényi’s model, which guarantees uniform probability distribution. For each generated graph we computed a straight-line drawing through the popular Fruchterman–Reingold force-directed algorithm [18]. We exploited the NetworkX Python library [22] both for generating the graphs and for computing their drawings. The resulting sizes of the crossing graphs is shown in Fig.˜8.

• $\mathrm{■}$

  real graphs: $12$ graphs with 30 to 379 vertices representing data from various real-world domains (see Table 1).They usually have higher density than the random graphs and, consequently, more edge crossings. All these graphs have been taken from the well-known Network Repository [40] (https://networkrepository.com). For each graph, we removed self-loops (if any) and computed a straight-line drawing with the implementation of Fruchterman–Reingold’s force-directed algorithm in NetworkX. ^{disabledisable}todo: disableTest a different drawing algorithm for the real graphs, since Fruchterman–Reingold produces drawings with many crossings. $\Rightarrow$ The drawing algorithms available to networkx (and pygraphviz) did not produce significantly better drawings than the algorithm by Fruchterman and Reingold.

We generate different types of crossing graphs that are planar. Recall that planar graphs are segment intersection graphs [10, 19]. Therefore, they always reflect the structure of some geometric graphs in terms of edge crossings.

• $\mathrm{■}$

  caterpillars: $60$ $n$-vertex caterpillar trees, $10$ instances chosen uniformly at random for each value of $n\in \{10,20,\mathrm{\dots },60\}$. First, we selected the diameter $\delta$ based on the probability of an $n$-vertex caterpillar to have such diameter; then we chose how to randomly attach the $n-\delta -1$ leaves to the $\delta -1$ internal vertices of the caterpillar [27]. We rejected with probability $0.5$ non-symmetric caterpillars, as they would have been generated twice. Due to the large integers involved in the computation, this method allowed us to generate caterpillars with up to $60$ vertices.

• $\mathrm{■}$

  trees: $80$ general trees, with $n\in \{10,20,\mathrm{\dots },80\}$ vertices; for each fixed $n$ we collected $10$ distinct instances, generated uniformly at random with the algorithm in [1]

• $\mathrm{■}$

  series-parallel graphs: $105$ series-parallel graphs, with $n\in \{10,20,\mathrm{\dots },70\}$ vertices and density $d\in \{1.2,1.4,1.6\}$. For each pair $(n,d)$ we collected $5$ instances, by repeatedly generating biconnected planar graphs using the OGDF library [11] (https://ogdf.uos.de/), and discarding those graphs that were not series-parallel.

• $\mathrm{■}$

  planar graphs: $180$ general connected planar graphs, with $n\in \{10,20,\mathrm{\dots },90\}$ and density $d\in \{1.2,1.6,2.0,2.4\}$. Precisely, we generated $5$ instances for each pair $(n,d)$, still using the random generator available in the OGDF library [11].

Since trees and caterpillars have treewidth $1$ and the treewidth of series-parallel graphs is $2$, these instances are of particular interest for evaluating the performances of the heuristics AG-1a2y, which works in polynomial-time for crossing graphs of bounded treewidth.

We performed the experiments on a Windows 11 Pro machine with an Intel Core i5-12500 CPU and 16 GB RAM. We used Gurobi [21] version 12.0.1 as ILP solver that used all available cores of the CPU. We implemented the heuristics in Python, using the NetworkX library [22].

On those instances for which the exact algorithm was able to finish the computation within the given time (see below), we compared the optimum with the value computed by the various heuristics. Precisely, we measured the ratio between the minimum frame size of the story computed by each heuristic and the minimum frame size of the story computed by the exact algorithm. With a slight abuse of terminology, we call this value the approximation ratio. For the random graphs and real graphs, the computation of the approximation ratio is restricted to the subset of crossing edges, because crossing-free edges persist in all frames of a planar graph story, regardless of the algorithm used to compute it.

For each instance, we also measured the runtime of each algorithm. We fixed an upper bound of $T=15$ minutes for the runtime allowed for the exact algorithm, and we recorded the value of the best solution achieved within $T$ (i.e., the incumbent solution). For those instances for which the runtime of the exact algorithm exceeded $T$, we also measured the optimality gap, that is, the gap between the incumbent solution (IS) and the upper bound (UB) estimated by the ILP solver at time $T$. In formula: $gap=\frac{UB-IS}{UB}$.

Furthermore, after verifying that, for all instances optimally solved by the exact algorithm, the heuristics were also able to produce a solution in less time, we set a maximum time limit of $T^{\prime }=10$ minutes for the heuristics based on Variant 1a, whose runtime may grow exponentially in the treewidth of the crossing graph. This was done to allow for faster experimentation, given the large number of instances. The instances for which Variant 1a could not finish within $T^{\prime }$ were considered unfeasible for AG-1a2a and AG-1a2b.

Fig.˜9 shows the percentage of instances per graph class that the ILP was able to solve within the given time limit of $T=15$ minutes ($900$ seconds). In each chart, the $x$-axis is the time in seconds and the $y$-axis (blue line) reports the number of instances solved optimally within the time at the corresponding $x$ coordinate. Fig.˜10 shows the optimality gap across the instances for each graph class (a point for each instance), where the instances were sorted by the number of crossings; points of instances with the same gap coincide in the chart.

Regarding the Geometric Graphs benchmark, more than half (55%) of the random graphs were solved optimally. In particular, all instances with 90 or less crossing edges were solved optimally in the given time, and 90% of the instances with 150 or less crossing edges were solved optimally. Conversely, only the two real graphs with small number of crossings (namely, the graphs bmw200 and ca-sandi_auths) could be solved optimally within $T$. However, for the graph rajat11 (which contains 290 crossings), the optimality gap is close to $0$ (namely, $0.08$). Overall, for most of the instances in the random graphs and real graphs, the optimality gap tends to increase with the number of edge crossings.

Regarding the Crossing Graphs benchmark, most of the series-parallel graphs (81.74%) and a high percentage of the trees (67.5%) and planar graphs (62.78%) could be solved optimally. Interestingly, more randomly sampled trees were solved than caterpillars (55.00%) in the given time. However, it is worth noting that the regular pattern observed in the optimality gaps for the caterpillars and trees is due to the fact that, for instances not solved to optimality within the time limit, the absolute difference between the best bound and the incumbent solution was exactly 1.

Full details on the runtime of all the heuristics can be found in the long version of the paper [5]. Heuristics AG-1b2a, AG-1b2b, AG-1c2a, and AG-1c2b computed all the instances of our graph benchmark very efficiently. On average they took less than $0.1$ seconds on the random graphs and about $0.34$ seconds on real graphs (the most expensive required about $1.6$ seconds). Also, they took less than $10$ milliseconds for the instances in the Crossing Graphs datasets. Runtime differences among these heuristics are negligible across Variants 2a and 2b for Phase 2, although 2a is slightly faster than 2b. The runtime is mostly affected by the variant chosen for Phase 1, where Variant 1b is a bit faster than Variant 1c, as expected.

Conversely, Variant 1a is significantly more expensive. We implemented it, using the Minimum Fill-in heuristic [8] to compute tree decompositions. For the analysis of the heuristics based on this variant, we took into account only those instances where a Pareto-optimal maximum pair of independent sets was found within the given time $T^{\prime }=10$ minutes. Variant 1a was able to find a solution for all the instances in the Crossing Graphs benchmark, as the Minimum Fill-in heuristic produced tree decompositions of width at most six for planar graphs and at most two for series-parallel graphs. For the random graphs, Variant 1a solved $137$ (of the $200$) instances within time $T^{\prime }$; the fraction of instances solved for each combination of the two parameters “number of nodes” and “width of the tree decomposition” is illustrated in the heatmap of Fig.˜6(e). For the real graphs, Variant 1a solved only 3/12 instances within $T^{\prime }$ (see Table 2).

Regarding the effectiveness of our heuristics, Table 3 summarizes the comparison over all instances that the exact algorithm managed within the given time $T=15$ minutes. Detailed results for the different types of graphs are reported in [5].

The results show that AG-1a2a and AG-1a2b achieve a $\sim 60\%$ optimality rate and an average approximation ratio of $\sim 95\%$, significantly outperforming the alternatives AG-1b2a/AG-1b2b and AG-1c2a/AG-1c2b in both metrics. The standard deviation of the approximation ratio for AG-1a2a and AG-1a2b remains below $10\%$, indicating consistent performance. Notably, for the trees and the caterpillars, AG-1a2a and AG-1a2b achieve near-perfect optimality rates ($97.0\%$ and $100.0\%$, respectively) with approximation ratios close to $100\%$. In contrast, the heuristics based on Variant 1b achieve fewer than $6\%$ optimal solutions on average, with lower approximation ratios around $68\%$. The heuristics using Variant 1c, while also exhibiting low optimality rates ($\sim 15\%$), maintain a stronger average approximation ratio of $\sim 83\%$ and a good standard deviation ($\sim 10.4\%$).

We remark that, for the real graphs the exact algorithm managed only 2 instances within the given time $T$, and AG-1a2a and AG-1a2b managed only 1 additional instance within the given time $T^{\prime }$. This data is not enough to get a clear picture of how the other heuristics compare on this dataset. However, by examining the data for all the instances in the real graphs dataset, we confirm that also in this case the heuristics based on Variant 1c outperformed those based on Variant 1b, with an improvement of about $29\%$ on average.

The exact algorithm typically handles geometric graphs with up to $90-100$ crossing edges in few minutes. However, it becomes generally impractical for real-world graphs that are locally dense and inevitably contain many more crossing edges. Regarding the heuristics, the difference between Variants 2a and 2b, in terms of both efficiency and effectiveness, is often negligible. A more detailed analysis of this phenomenon is given in [5]. Conversely, the choice of the variant for Phase 1 makes a big difference, namely:

• $\mathrm{■}$

  The heuristics based on Variant 1a yield solutions close to the optimum in many cases. However, they become computationally unfeasible for graphs with high number of nodes or with crossing graphs of high treewidth; in particular, they exhibit more or less the same limits as the exact algorithm on the real graphs, although they make it possible to manage all instances in the Crossing Graphs benchmark.

• $\mathrm{■}$

  The heuristics based on Variant 1c offer the best trade-off between efficiency and effectiveness. They perform fast on all instances and maintain high average approximation ratios (approximately $80\%-88\%$, depending on the graph class).

In addition to ensuring drawing stability and low visual complexity, our model promotes smooth transitions between consecutive frames (i.e., minimal local changes from one frame to the next), as only the current edges that intersect the upcoming edge are removed. However, this approach may result in long stories. To balance these aspects, we can compress a planar story by allowing multiple edges to be inserted simultaneously: for each subsequence of consecutive, pairwise non-crossing edges, all of them can be added at once. In this way, the resulting compressed story remains planar, and its smallest frame is at least as large as that of the original story. Nonetheless, enabling multiple edges to enter simultaneously in the visualization motivates the design of dedicated algorithms aimed at producing short stories while still maximizing the minimum frame size.

We focused on constructing a planar story of geometric graphs, i.e., of graphs with a given drawing. It would be interesting to investigate how different drawings of the same graph affect the quality of the story. Furthermore, what kind of crossing graphs would allow us to construct good edge stories?

Our heuristics based on Variants 1b and 1c are fast enough to solve also more complex instances than those in our benchmark. It would be interesting to investigate whether the quality of these variants could be improved by using different heuristics for choosing the independent sets for the initial and final frames than just adding vertices of minimum degree. See, e.g., [20] for a list of heuristics for computing large independent sets.

Regarding the problem complexity: Is MaxMinFramePlanarStoryD($G$,$m$) NP-complete for $3$-plane graphs? Is the problem in FPT parameterized by the treewidth of the crossing graph of $G$? Is Advanced Greedy 1a a constant-factor approximation algorithm?