Graphs laid out by ForceAtlas2 with augmenting edges colored red. (a)
augmented grid (redraw), (b) augmented grid weighted by the heuristic
($H_{\textrm{min}}$), (c) triangulations (redraw), (d) triangulations weighted
by the heuristic ($H_{\textrm{min}}$)

# Identifying Cluttering Edges in Near-Planar Graphs

S. van Wageningen10000-0002-0346-5597 and T. Mchedlidze10000-0001-6249-3419
and A. Telea10000-0003-0750-0502
1Utrecht University, The Netherlands

###### Abstract

Planar drawings of graphs tend to be favored over non-planar drawings. Testing
planarity and creating a planar layout of a planar graph can be done in linear
time. However, creating readable drawings of nearly planar graphs remains a
challenge. We therefore seek to answer which edges of nearly planar graphs
create clutter in their drawings generated by the mainstream graph drawing
algorithms. We present a heuristic to identify problematic edges in nearly
planar graphs and adjust their weights, in order to produce higher quality
layouts with spring-based drawing algorithms. Our experiments show that the
heuristic produces significantly higher quality drawings for augmented grid
graphs, augmented triangulations and deep triangulations. <ccs2012> <concept>
<concept_id>10003120.10003145.10003146.10010892</concept_id>
<concept_desc>Human-centered computing Graph drawings</concept_desc>
<concept_significance>500</concept_significance> </concept> </ccs2012>

[500]Human-centered computing Graph drawings

††volume: 42††issue: 3

##  1 Introduction

The ultimate goal when constructing a readable drawing of a graph (i.e. node-
link diagram) is to avoid clutter that prevents viewer from grasping the
graph’s structure. One of the quality metrics that measures the clutter of a
graph drawing is the number of edge crossings. It is long known that humans
perform better on shortest path related tasks in drawings with fewer crossing
[Pur97]. Humans also tend to prefer such drawings [MBK96, vHR08]. It is
therefore natural to request that a drawing of a graph possesses no edge
intersections at all, whenever possible. Such drawings, and the graphs that
can be drawn in such a way, are called _planar_. Fortunately, detecting
whether a graph has a planar drawing [HT74] and constructing one in
affirmative[Tam13b] can be done in linear time. In practice, on the other
hand, graphs are rarely planar. However, they can still be sparse, or contain
clear planar substructures, in other words, be _nearly planar_. It is
therefore desirable for such graphs to achieve _nearly planar_ drawings.

There are various attempts to formalize the notion of _near-planarity_ and
construction of nearly planar drawing. Unfortunately, all of these attempts
lead to hard computational problems [GJ83, CM13, ABS11, KM13]. There are a few
spring-based algorithms that address certain readability issues relevant to
near-planarity, such as trying to keep crossing angles close to $90^{\circ}$
[ABS12] or improving layouts by preserving existing crossings [SAAB11]. Yet,
there is a lot of room for further work to generate practical working
algorithms that construct readable drawings of near planar graphs.

In this paper we propose a spring-based heuristic approach to construct nearly
planar drawing of graphs that contain dense planar substructures. This work is
motivated by the lack of comparable approaches, and the aforementioned
hardness of formal definitions of near-planarity. We conduct an experimental
evaluation comparing our approach to the state-of-the-art spring-based
algorithms.

The paper is structured as follows. In Section 3, we present initial
observations on how to resolve clutter in near planar drawings, and provide an
initial experiment that lies in the background of our approach. In Section 4,
we present our heuristic. Section 5 describes the experimental setup, whereas
Section 6 presents the results of our experiments.

##  2 Related work

Throughout the paper we denote by $G=(V,E,w)$ a graph, with $V$, $E$ being the
sets of nodes, edges, respectively and $w:E\rightarrow\mathbb{R}$ the edge-
weighting function. Here $n=|V|$ and $m=|E|$. For nodes $u$ and $v$, we denote
by $e=\\{u,v\\}$ and $e=(u,v)$, an undirected edge and a directed edge.

### Theoretical approaches to near-planarity

Since a planar drawing is the one that does not contain any crossing, the most
straight-forward idea to define near-planarity is to request a drawing with as
few crossings as possible [CM13]; this problem is NP-hard [GJ83] even for a
planar graph plus a single edge [CM13]. There are a few algorithms that insert
edges into planar graphs and their drawings in a crossing optimal way [RR22,
GKM08, GMW05, CH16, CG12], of which have been compared experimentally [GM03].

While we know that humans perform tasks well on planar layouts [Pur97], it has
been also shown experimentally that the negative effects of the crossings on
the task performance decreases as the edge crossing angles increase [HHE08].
This led to the definition of RAC [DEL11] and $\alpha$-AC drawings [GDLM11].
Deciding whether such drawings exist is NP-hard as well [ABS11]. If the graph
is sparse it is also natural to try to limit how many crossings an edge has,
as fewer crossings would impair less the perception of the edge. This idea led
to definition of _k-planar_ and _quasi-planar_ drawings. However, again,
recognizing whether a graph has these kind of drawings is NP-complete [KM13].

### Heuristics

A plethora of spring-based algorithms produce high-quality layouts without
specifically targeting nearly planar graphs [Tam13a]. Out of these approaches,
we refer specifically to ForceAtlas2 (_FA2_) [JVHB14, Chi19] and Stress
Majorization (_SM_) [GKN04] which are powerful layout techniques that we use
for our experiments, since they are often compared with novel techniques
[WJW∗19, KCM18]. SM solely bases the spring forces between all pairs of nodes
on the length of their shortest paths, whereas FA2 considers attractive and
repulsive forces to compute node spring forces. Additionally, the work on SM
[GKN04] suggests to weight node pairs by taking into account the number of
common neighbors. Here, the weight of a node-pair $u,v$ is set as:
$w(u,v)=|N_{u}\cup N_{v}|-|N_{u}\cap N_{v}|$, where $N_{u}$ denotes the
neighborhood of node $u$. This idea improves the performance of SM when edge
lengths need to vary significantly. As will become clear in the following,
this approach is relevant to ours and is therefore included as the
_neighborhood weighting function_ in our experiments.

Finally, relevant to near-planarity, Argyriou et al. [ABS12] present an
approach that maximizes the _total resolution_ , which is the minimum of the
_angular_ and _crossing_ resolution. While ImPrEd [SAAB11] preserves the
topology of the given layout and therefore its planarity. Similarly, tsNET⋆
[KRM∗17] tends to preserve a layout’s original structure by favoring
occasional long edges and thus unfolding the layout.

##  3 Preliminaries

Our overarching goal is to produce a drawing of a nearly planar graph $G$
which clearly depicts its planar substructure. This statement itself hints us
to distinguish among the graph edges that contribute to its planar
substructure and those that destroy it. If we were able to detect the latter
edges, we could remove them, construct a planar drawing of the remaining graph
(using e.g. [dFPP90, Sch90]), and place the earlier removed edges back. There
are two challenges that prevent us from taking this approach. The first one is
that detecting a dense planar substructure is a hard optimization problem
known as _Maximum planar subgraph_ [Cim95]. The second is that such an
approach would inevitably be based on algorithms to construct planar drawings
of planar graphs, e.g. [dFPP90, Sch90], which are relatively hard to implement
and up to date are not part of most graph drawing libraries and applications.
Therefore, we chose to attack our problem using a relatively simple heuristic
based on a spring-based approach.

An initial idea was to identify such _planarity-destroying_ edges. Once
identified, we would weight them with relatively lower weights than regular
edges. We would then use a state-of-the-art spring-based approach, that takes
edge-weights into account. Our hope was that the planarity-destroying edges
would influence the layout less than the remaining edges and therefore the
planar substructure would reveal itself in the drawing.

Figure 1: (a) Augmented grid (b), weighted augmented grid

To test whether this idea is feasible, we perform the following initial
experiment. We consider a grid $D=(V,E)$ and construct a graph $G=(V,E\bigcup
E_{p})$, where $E_{p}$ is a set of random edges on the vertex set $V$ with the
property that $E\bigcap E_{p}=\emptyset$. We call this graph an _augmented
grid_. Starting with a random initial coordinate assignment, we draw an
augmented grid using FA2. These layouts (see Figure 1), appear cluttered and
folded inwards, and of poor quality. We then reduce the weights of the edges
in $E_{p}$ to $0.01$ and rerun FA2. The resulting layout (Figure 1) has
unfolded and has become a near perfect depiction of a grid graph. This
experiment hints that knowing the planarity-destroying edges can be useful in
depicting planar substructures in nearly planar graphs, using a spring-based
approach and appropriate edge weighting scheme.

In our experiments with other augmented planar graph classes, we observe that
not only the planarity-destroying edges create clutter in the drawing, but so
do the edges that are close to the outer face. These observations led to the
following questions: Which edges of a given nearly planar graph $G$ create
clutter in the drawings of $G$ generated by a spring-embedding algorithm?
Using a spring-based approach, how do we weight these edges to create a
drawing where a planar substructure is clearly visible? We call such edges
_cluttering_ and address the stated questions in the following section. The
Python implementation of the heuristic can be found on GitHub.

##  4 Finding and weighting cluttering edges

### Vertex-disjoint paths

Our approach to identify cluttering edges is based on the following intuition.
If the end-vertices of an edge $e=\\{u,v\\}$ are connected by multiple,
relatively short paths in the graph, then the edge $e$ can also be short. In
the opposite case, where there are only relatively long paths between $u$ and
$v$, then the edge $e$ could collapse the drawing and therefore could be a
cluttering one. However, finding all paths between even a single pair of
vertices will result in exponential computations. Hence, we use as a proxy the
lengths of the vertex-disjoint paths between $u$ and $v$.

Figure 2: A grid with three gray augmenting edges $\\{a,b\\}$, $\\{c,d\\}$ and
$\\{u,w\\}$. Vertex-disjoint paths are depicted by colors. The footprints of
$\\{a,b\\}$, $\\{c,d\\}$ are $f(\\{c,d\\})=[2,2,6,6]$,
$f(\\{a,b\\})=[7,8,8,12]$. Note that a footprint of edge $\\{c,d\\}$, that
need to be short in a grid-revealing layout, contains small values. While the
footprint of the long edge $\\{a,b\\}$ contains mostly large values. Observe
that footprint of $\\{a,b\\}$ uses another augmenting edge and thus can also
contain smaller numbers but they are relatively fewer and larger than the
numbers in the footprints of short edges.

Vertex-disjoint paths can be found using the max-flow Edmonds-Karp algorithm
[EK72], as described in [KT06]. For completeness, we summarize the idea of
this reduction here. A directed graph with edge-weights of value $1$ has $k$
edge independent paths between two vertices $u$ and $v$ if and only if it has
a flow of value $k$ between $u$ and $v$. To reduce the undirected problem to
the directed, we substitute every undirected edge $\\{u,v\\}$ by two $(u,v)$
and $(v,u)$. To ensure that the paths are vertex disjoint, we substitute every
node $u$ by two $u_{s}$ and $u_{t}$, add to the graph directed edge
$(u_{s},u_{t})$ and substitute every edge $(w,u)$, incoming to $u$, by
$(w,u_{s})$; analogously, substitute every edge $(u,w)$, outgoing from $u$, by
$(u_{t},w)$. In the following, for an edge $e=\\{u,v\\}$, we denote by
$f(e)=[\ell_{1},\ell_{2},\dots]$ the sequence of the lengths of the vertex-
disjoint paths between $u$ and $v$ in $G\setminus e$, listed in non-decreasing
order, and call $f(e)$ the _footprint_ of $e$. Given that the complexity of
Edmond-Karp’s algorithm is $O(VE^{2})$, computation of footprints for all
edges of $G$ takes $O(VE^{3})$ time.

### Outlier detection

By analyzing the footprints of edges in augmented grids, we observe patterns
that distinguish the edges that need to stay short in a grid-revealing layout
and those that need to get long in such layouts. Refer to Figure 2 for a
detailed example. These differences in the footprints brings us the idea of
using an outlier detection algorithm to detect cluttering edges. We experiment
with the _Isolation Forest_ technique [LTZ12] which is designed to find
anomalous data points in n high-dimensional space. Intuitively, the Isolation
Forest method isolates a single specific data point by creating partitions
through selecting random cutoff points along different dimensions. Once the
data point is completely isolated, the number of partitions inform whether the
point is anomalous or not. Few required partitions indicate an anomalous
behavior. This partitioning process is applied to every data point, and
subsequently repeated to get an average estimate. The time-complexity of the
technique is $\mathcal{O}(s(m+p)p)$, where $s$ is the number of times the
technique is repeated, and $p$ is the number of partitions needed to isolate a
node. The Isolation Forest is a simple but effective technique, and can be
applied to detect _outlier_ edges according to their footprints in linear time
.

### Footprint normalization and cluttering edge weighting

Before however applying the Isolation Forest method to footprints of the
edges, we have to make sure that they all have the same length. For this
purpose, we expand or contract the footprints, depending on the user-specified
number of dimensions $k$ and function $\mathcal{M}$, which can be either the
minimum, maximum or mean function. Equation 1 portrays how the footprints are
expanded or contacted, given a footprint $f(e)$ of initial length $l$ and a
desired length $k$.

$f^{\prime}(e)=\begin{cases}f(e)\oplus[{\mathcal{M}}(f(e))]_{k-l}&l<k\\\
f(e)&l=k\\\ f(e)[0:k-1]\oplus{\mathcal{M}}(f(e)[k:l])&l>k\\\ \end{cases}$ (1)

In our experiments we evaluate the results for all aforementioned choices of
function $\mathcal{M}$, i.e. minimum, maximum or mean. Based on multiple
experiments, we set the weight of edge $e$ to $\mathcal{M}(f(e))$.

##  5 Experimental setup

_Dataset_ | $n_{min}$ | $n_{max}$ | $m_{min}$ | $m_{max}$ |  #_Graphs_
---|---|---|---|---|---
Grids | 48 | 196 | 86 | 383 | 50
Triangulations | 26 | 100 | 69 | 297 | 50
Deep triangulations | 25 | 98 | 86 | 367 | 50
Rome | 18 | 100 | 25 | 141 | 100
Table 1: Statistics of datasets used in the experiments

Let $G=(V,E)$ be a nearly planar graph. To evaluate our approach, we apply
spring-based algorithms to the weighted graph $G_{\mathcal{M}}=(V,E,w)$,
$w(e)=\mathcal{M}(f(e))$ and the baseline unweighted graph $G=(V,E)$. We
compare the obtained drawings both qualitatively, by exploring them visually,
and quantitatively, by employing several quality metrics. In the following, we
discuss the datasets used for the experiment, the way the layouts are
computed, and the measured quality metrics.

### Datasets

We used four types of graphs, as follows (see Table 1).

Grids: We start with a grid with a random number of rows and columns ranging
between $6$ and $14$. Next, we add $0.1|V|$ edges between random non-adjacent
nodes to destroy the grid structure, yielding the _augmented grid_. Note that
most, but not every, such added edge introduces edge crossings.

Triangulations: These graphs are generated by applying Delaunay triangulation
algorithm (implemented in SciPy) on random 2D point sets, to which structure-
destroying edges are added similarly as to the Grids. We call these graphs
_augmented triangulations_. For a grid or a triangulation $G$, we denote by
$\overline{G}$ its augmented version.

Deep triangulations: Even planar graphs can be a challenge for spring-based
approaches when it comes to unraveling their planar structure, especially when
the planar-layout edges need to have various lengths. This is the case for
planar graphs that contain small cycles with many vertices inside them. To
further test our approach, we construct so called _deep triangulations_ , as
follows: (1) Randomly place $0.7|V|$ of the vertices and construct their
Delaunay triangulation $T$. (2) Place a random number of points $r<0.3|V|$ in
a random triangle $t\in T$. (3) Apply Delaunay triangulation of the $r$ points
in $t$ to create new edges. (4) Repeat steps 2 and 3 steps until all remaining
$0.3|V|$ vertices have been placed.

Rome: We also include a subset of non-planar _Rome_ graphs [GDT] into our
experiment. Note that grids and (deep) triangulations contain dense planar
substructures and therefore we expect our heuristic to be able to find
cluttering edges in these graphs. However, we also include Rome graphs to our
experiments, to check whether our technique generalizes to this fairly popular
graph benchmark [WYHS21], which however are very sparse and do not contain
dense planar substructures.

Figure 3: (a) deep triangulations (orig), (b) deep triangulations weighted by
$H_{\textrm{min}}$, (c) Rome (orig), (d) Rome weighted by $H_{\textrm{min}}$

### Layouts

We create layouts using the spring-based methods _FA2_ and _SM_. For each grid
or triangulation $G$ and each spring-method $\mathcal{S}$, we compute seven
layouts:

  * •

$\texttt{orig}\equiv\mathcal{S}(G)$ – spring-embedding of a graphs $G$,

  * •

on_top – drawing $\mathcal{S}(G)$ with edges of $\overline{G}\setminus G$
appended on top of the drawing, where $\overline{G}$ is the augmented version
of graphs $G$,

  * •

$\texttt{redraw}\equiv\mathcal{S}(\overline{G})$ – spring-embedding of
$\overline{G}$,

  * •

$H_{\textrm{min}}\equiv\mathcal{S}(\overline{G}_{\textrm{min}})$,
$H_{\textrm{max}}\equiv\mathcal{S}(\overline{G}_{\textrm{max}})$,
$H_{\textrm{mean}}\equiv\mathcal{S}(\overline{G}_{\textrm{mean}})$ – spring-
embeddings of $\overline{G}$ where outlier edges are weighted according to the
functions min, max and mean, respectively (see Eqn. 1), jointly referred to as
heuristic layouts,

  * •

$H_{\textrm{nb}}\equiv\mathcal{S}(\overline{G}_{\textrm{nb}})$ – spring-
embeddings of $\overline{G}$ where node-pairs are weighted using the
neighborhood weighting function.

For the deep triangulations and Rome graphs, which are challenging by
themselves, we do not consider augmented versions, thus on_top and redraw are
not computed for them. We run FA2 and SM five times for each graph, and choose
the best layout, w.r.t. to the number of crossings. Both SM and FA2 are run
for a maximum of 2000 iterations with default settings.

### Quality Metrics

We quantitatively evaluate the results by computing three quality metrics: the
crossing number, $\mathtt{nc}\in[0,\infty]$ – the total number of crossings in
a layout; the angular resolution, $\mathtt{ang\\_res}\in[0,1]$ – the minimum
angle between any two incident edges normalized by $2\pi/\max_{v\in
V}{\textrm{deg}(v)}$, and crossing resolution, $\mathtt{cros\\_res}\in[0,1]$ –
the minimum angle of any two crossing edges normalized by $\pi/2$.
Additionally, in order to measure how the augmenting edges distort the
layouts, we compute the Procrustes Statistic [CC00], $\mathtt{ps}\in[0,1]$.
Here, a value of $0$ indicates that two layouts are exactly similar in the
positions of vertices, after rotation, translation and scaling. Finally, we
note that while stress[DLF∗09] is a common function to evaluate layout
quality, we do not use it in our evaluation, since layouts that show well
planar substructures in planar graphs do not have low stress, since in such
layouts some edges are (much) longer than the optimal value dictated by
stress.

##  6 Results and Discussion

### Qualitative analysis

Representative examples of running FA2 on augmented graphs (redraw) are
depicted in Figures Identifying Cluttering Edges in Near-Planar Graphs,
Identifying Cluttering Edges in Near-Planar Graphs and 5. Here, the outer
faces appear cluttered and the layouts appear to be folded inwards. Figures
Identifying Cluttering Edges in Near-Planar Graphs and Identifying Cluttering
Edges in Near-Planar Graphs show the layouts where edges are weighted
according to the heuristic. We observe that the augmenting edges look longer,
this makes the layouts being less folded inwards, which in turn removes
clutter and brings the grid-like and triangulation structures forward. The
results of the heuristic on deep triangulations (Figure 3, 3) also show some
improvements in the clutter, especially in the outer face. Finally, for the
Rome graphs (Figures 3, 3), we do not see any improvement in the quality of
the layout. However, this result is expected, as Rome graphs do not contain
dense plain substructures.

### Quantitative analysis

Figure 4: Number of crossings of grids and triangulations in FA2 layouts
described in Section 5. Black lines represent the median

Figure 4 shows the distributions of the number of crossings of the seven
layouts described in Section 5 for the augmented triangulations and grids (red
and blue, respectively). We see that number of crossings in the heuristic
layouts tend to be lower compared to the redraw layouts produced by pure
spring-embedder. We also notice that the nb layouts, produced using
neighborhood weighting function, show no change in the number of crossings, in
comparison to the redraw layouts.

Tables 2 shows the median values of the quality metrics of layouts of all
datasets. Since the data are paired but non-normally distributed, we use the
two-sided Wilcoxon signed rank test to indicate significant ($\alpha=0.05)$
improvement or deterioration in a quality metric. For the grids and
triangulations we measure whether there is a significant difference between
the heuristic and the redraw layouts. Whereas, for deep triangulations and
Rome graphs we compare the heuristic with the orig layout.

Regarding the number of crossings, we observe significant improvements on the
heuristic layouts of the augmented grids and (deep) triangulations graphs.
Additionally, the heuristic approach outshines the neighborhood technique for
these graphs. As expected from the qualitative analysis, for the Rome graphs
the heuristic layouts are either equally good ($H_{\textrm{max}}$) or
significantly worse ($H_{\textrm{mean}}$, $H_{\textrm{min}}$) w.r.t the number
of crossings.

Regarding angular resolution, we observe significant improvements over the
redraw layouts in the augmented grids when FA2 is used. Whereas SM scores
significantly worse for both the triangulations and Rome graphs. For the
crossing resolution, we observe no significant differences for the heuristic
over the orig layouts for the augmented grids, triangulations and deep
triangulations. However, the heuristic layouts are significantly worse for the
Rome graphs, as expected from the structure of the Rome graphs and the
intention of our heuristic.

Additionally, we note that the Procrustes Statistic values for the heuristic
layouts tend to be close to 0, for all but the Rome dataset. These results
indicate that the weighting tactic of our heuristic yields layouts that stay
close to the original planar structure. Lastly, we observe that FA2 scores
better than SM on most metrics for all datasets.

Grids | $\mathtt{nc}$ | $\mathtt{ang\\_res}$ | $\mathtt{cros\\_res}$ | $\mathtt{ps}$
---|---|---|---|---
orig | 0 | 0 | .631 | .982 | - | - | - | -
on_top | 52 | 52 | .011 | .005 | .10 | .16 | 0 | 0
redraw | 67 | 102 | .014 | .018 | .14 | .12 | .11 | .25
$H_{\textrm{mean}}$ | 51 | 52 | .027 | .020 | .14 | .14 | .02 | .02
$H_{\textrm{min}}$ | 51 | 52 | .030 | .020 | .11 | .14 | .02 | .02
$H_{\textrm{max}}$ | 51 | 52 | .028 | .020 | .14 | .14 | .02 | .02
$H_{\textrm{nb}}$ | 60 | 94 | .019 | .026 | .17 | .12 | .11 | .19
Triangulations
orig | 53 | 79 | .009 | .023 | .10 | .14 | - | -
on_top | 96 | 131 | .008 | .016 | .08 | .10 | 0 | 0
redraw | 87 | 154 | .009 | .019 | .12 | .12 | .03 | .08
$H_{\textrm{mean}}$ | 63 | 88 | .015 | .012 | .12 | .12 | .02 | .06
$H_{\textrm{min}}$ | 63 | 88 | .012 | .012 | .11 | .12 | .02 | .06
$H_{\textrm{max}}$ | 65 | 88 | .013 | .012 | .12 | .12 | .02 | .06
$H_{\textrm{nb}}$ | 93 | 124 | .013 | .015 | .10 | .09 | .04 | .07
Deep triangulations
orig | 74 | 102 | .017 | .020 | .13 | .15 | - | -
$H_{\textrm{mean}}$ | 59 | 82 | .010 | .022 | .11 | .13 | .03 | .09
$H_{\textrm{min}}$ | 61 | 82 | .019 | .022 | .12 | .13 | .03 | .09
$H_{\textrm{max}}$ | 58 | 82 | .016 | .022 | .16 | .13 | .03 | .09
$H_{\textrm{nb}}$ | 73 | 91 | .017 | .023 | .10 | .13 | .03 | .04
Rome
orig | 26 | 30 | .048 | .065 | .30 | .26 | - | -
$H_{\textrm{mean}}$ | 28 | 34 | .035 | .029 | .21 | .15 | .38 | .53
$H_{\textrm{min}}$ | 29 | 34 | .033 | .029 | .18 | .15 | .34 | .53
$H_{\textrm{max}}$ | 24 | 34 | .037 | .029 | .21 | .15 | .35 | .53
$H_{\textrm{nb}}$ | 25 | 25 | .052 | .062 | .27 | .29 | .13 | .18
Table 2: Median values of metrics. For grids and triangulations, redraw is
compared with heuristic layouts. For deep triangulations and Rome, orig is
compared with heuristic layouts. A stronger hue indicates a significant
result, with FA2 & SM

##  7 Conclusion

We presented a heuristic to detect edges that create clutter in layouts of
near planar graphs. By suitably weighting such edges, we use spring-embedders
to draw these graphs with the goal to better convey their planar
substructures. The experiments indicate that our heuristic produces better
results for augmented grids and triangulations. For deep triangulations we
noticed visual improvements and clutter decrease in the outer face, though
further improvements are possible. Moreover, our heuristic produces drawings
with fewer number of crossings than conventional methods for all but the Rome
graphs. This result is, however, expected since the Rome graphs do not contain
dense planar substructures. Future work can yield more insight into deep
triangulations, which we expect to be very challenging to lay out in a way
that reveal their planar structure. Moreover, additional comparisons can be
made between our heuristic and tsNET⋆. In addition to more experiments, future
work can attempt to improve the heuristic’s limiting time complexity, by
altering or substituting the vertex-disjoint path and outlier detection
computations. Finally, we plan to test whether Graph Neural Networks can be
more successful in identifying cluttering edges.

Figure 5: ForceAtlas2 layouts (left to right) orig, on_top, redraw
$H_{\textrm{min}}$, $H_{\textrm{max}}$, $H_{\textrm{mean}}$ and
$H_{\textrm{nb}}$ for several graphs

## References

  * [ABS11] Argyriou E. N., Bekos M. A., Symvonis A.:  The straight line rac drawing problem is np-hard.  In _SOFSEM 2011: Theory and Practice of Computer Science_ (Berlin, Heidelberg, Germany, 2011), vol. 6543 of _LNCS_ , Springer, pp. 77–85.  doi:10.1007/978-3-642-18381-2_6.
  * [ABS12] Argyriou E., Bekos M., Symvonis A.:  Maximizing the Total Resolution of Graphs.  _The Computer Journal 56_ , 7 (06 2012), 887–900.  doi:10.1093/comjnl/bxs088.
  * [CC00] Cox T., Cox M. A.:  _Multidimensional scaling_.  Chapman and Hall/CRC, 2000.
  * [CG12] Chimani M., Gutwenger C.:  Advances in the planarization method: Effective multiple edge insertions.  _Journal of Graph Algorithms and Applications 16_ , 3 (2012), 729–757.  doi:10.7155/jgaa.00264.
  * [CH16] Chimani M., Hlinený P.:  Inserting multiple edges into a planar graph.  In _32nd International Symposium on Computational Geometry_ (Boston, MA, USA, 2016), Fekete S. P., Lubiw A., (Eds.), vol. 51 of _LIPIcs_ , Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 30:1–30:15.  doi:10.4230/LIPIcs.SoCG.2016.30.
  * [Chi19] Chippada B.:  Forceatlas2 python.  URL: https://github.com/bhargavchippada/forceatlas2.
  * [Cim95] Cimikowski R. J.:  An analysis of some heuristics for the maximum planar subgraph problem.  In _Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms_ (San Francisco, California, USA, 1995), Clarkson K. L., (Ed.), ACM/SIAM, pp. 322–331.  URL: http://dl.acm.org/citation.cfm?id=313651.313713.
  * [CM13] Cabello S., Mohar B.:  Adding one edge to planar graphs makes crossing number and 1-planarity hard.  _SIAM Journal on Computing 42_ , 5 (2013), 1803–1829.  doi:10.1137/120872310.
  * [DEL11] Didimo W., Eades P., Liotta G.:  Drawing graphs with right angle crossings.  _Theoretical Computer Science 412_ (2011), 5156–5166.
  * [dFPP90] de Fraysseix H., Pach J., Pollack R.:  How to draw a planar graph on a grid.  _Comb. 10_ , 1 (1990), 41–51.  doi:10.1007/BF02122694.
  * [DLF∗09] Dwyer T., Lee B., Fisher D., Quinn K. I., Isenberg P., Robertson G., North C.:  A comparison of user-generated and automatic graph layouts.  _IEEE Transactions on Visualization and Computer Graphics 15_ , 6 (2009), 961–968.  doi:10.1109/TVCG.2009.109.
  * [EK72] Edmonds J., Karp R. M.:  Theoretical improvements in algorithmic efficiency for network flow problems.  _Journal of the ACM 19_ (1972), 248–264.  doi:10.1145/321694.321699.
  * [GDLM11] Giacomo E. D., Didimo W., Liotta G., Meijer H.:  Area, curve complexity, and crossing resolution of non-planar graph drawings.  _Theory Comput. Syst. 49_ , 3 (2011), 565–575.  doi:10.1007/s00224-010-9275-6.
  * [GDT] GDToolkit:  Rome graphs.  URL: http://www.graphdrawing.org/data.html.
  * [GJ83] Garey M. R., Johnson D. S.:  Crossing number is np-complete.  _SIAM Journal on Algebraic and Discrete Methods 4_ (1983), 312–316.
  * [GKM08] Gutwenger C., Klein K., Mutzel P.:  Planarity testing and optimal edge insertion with embedding constraints.  _J. Graph Algorithms Appl. 12_ , 1 (2008), 73–95.  doi:10.7155/jgaa.00160.
  * [GKN04] Gansner E. R., Koren Y., North S.:  Drawing by stress majorization.  In _Graph Drawing_ (Berlin, Heidelberg, Germany, 2004), Pach J., (Ed.), vol. 3383 of _LNCS_ , SPRINGER.  doi:10.1007/978-3-540-31843-9_25.
  * [GM03] Gutwenger C., Mutzel P.:  An experimental study of crossing minimization heuristics.  In _Graph Drawing_ (Perugia, Italy, 2003), vol. 2912 of _LNCS_ , Springer, pp. 13–24.  doi:10.1007/978-3-540-24595-7\\_2.
  * [GMW05] Gutwenger C., Mutzel P., Weiskircher R.:  Inserting an edge into a planar graph.  _Algorithmica 41_ , 4 (2005), 289–308.  doi:10.1007/s00453-004-1128-8.
  * [HHE08] Huang W., Hong S.-H., Eades P.:  Effects of crossing angles.  In _2008 IEEE Pacific Visualization Symposium_ (2008), pp. 41–46.  doi:10.1109/PACIFICVIS.2008.4475457.
  * [HT74] Hopcroft J., Tarjan R. E.:  Efficient planarity testing.  _Journal of the Association for Computing Machinery 21_ (1974), 549–568.  doi:10.1145/321850.321852.
  * [JVHB14] Jacomy M., Venturini T., Heymann S., Bastian M.:  Forceatlas2, a continuous graph layout algorithm for handy network visualization designed for the gephi software.  _PLOS ONE 9_ (2014).  doi:10.1371/journal.pone.0098679.
  * [KCM18] Kwon O.-H., Crnovrsanin T., Ma K.-L.:  What would a graph look like in this layout? a machine learning approach to large graph visualization.  _IEEE Transactions on Visualization and Computer Graphics 24_ (2018), 477–488.  doi:10.1109/TVCG.2017.2743858.
  * [KM13] Korzhik V. P., Mohar B.:  Minimal obstructions for 1-immersions and hardness of 1-planarity.  _Journal of Graph Theory 72_ (2013), 30–71.
  * [KRM∗17] Kruiger J., Rauber P., Martins R., Kerren A., Kobourov S., Telea A.:  Graph layouts by t-sne.  _Computer Graphics Forum 36_ (06 2017), 283–294.  doi:10.1111/cgf.13187.
  * [KT06] Kleinberg J. M., Tardos É.:  _Algorithm design_.  Addison-Wesley, 2006.
  * [LTZ12] Liu F. T., Ting K. M., Zhou Z.-H.:  Isolation-based anomaly detection.  _ACM Trans. Knowl. Discov. Data 6_ , 1 (2012).  doi:10.1145/2133360.2133363.
  * [MBK96] McGrath C., Blythe J., Krackhardt D.:  Seeing groups in graph layout.  _Connections 19_ (1996), 22–29.
  * [Pur97] Purchase H.:  Which aesthetic has the greatest effect on human understanding?  In _Graph Drawing_ (Berlin, Heidelberg, Germany, 1997), Dibattista G., (Ed.), vol. 1353 of _LNCS_ , Springer, pp. 248–261.  doi:10.1007/3-540-63938-1_67.
  * [RR22] Radermacher M., Rutter I.:  Inserting an edge into a geometric embedding.  _Computational Geometry 102_ (2022), 101843.  doi:10.1016/j.comgeo.2021.101843.
  * [SAAB11] Simonetto P., Archambault D., Auber D., Bourqui R.:  Impred: An improved force-directed algorithm that prevents nodes from crossing edges.  _Comput. Graph. Forum 30_ , 3 (2011), 1071–1080.  doi:10.1111/j.1467-8659.2011.01956.x.
  * [Sch90] Schnyder W.:  Embedding planar graphs on the grid.  In _Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms_ (San Francisco, California, USA, 1990), Johnson D. S., (Ed.), SIAM, pp. 138–148.  URL: http://dl.acm.org/citation.cfm?id=320176.320191.
  * [Tam13a] Tamassia R.:  _Force-Directed Drawing Algorithms_.  Chapman and Hall/CRC, 2013.
  * [Tam13b] Tamassia R.:  _Planar straight line drawing algorithms_.  Chapman and Hall/CRC, 2013.
  * [vHR08] van Ham F., Rogowitz B.:  Perceptual organization in user-generated graph layouts.  _IEEE Transactions on Visualization and Computer Graphics 14_ , 6 (2008), 1333–1339.  doi:10.1109/TVCG.2008.155.
  * [WJW∗19] Wang Y., Jin Z., Wang Q., Cui W., Ma T., Qu H.:  Deepdrawing: A deep learning approach to graph drawing.  In _IEEE Transactions on Visualization and Computer Graphics_ (2019).  doi:10.48550/ARXIV.1907.11040.
  * [WYHS21] Wang X., Yen K., Hu Y., Shen H.:  Deepgd: A deep learning framework for graph drawing using gnn.  _IEEE Computer Graphics and Applications 41_ , 05 (2021), 32–44.  doi:10.1109/MCG.2021.3093908.


# Categorizing Readout Error Correlations on Near Term Quantum Computers

Benjamin Nachman<EMAIL_ADDRESS>Physics Division, Lawrence Berkeley
National Laboratory, Berkeley, CA 94720, USA  Michael R. Geller  Center for
Simulational Physics, University of Georgia, Athens, Georgia 30602, USA

###### Abstract

Readout errors are a significant source of noise for near term quantum
computers. A variety of methods have been proposed to mitigate these errors
using classical post processing. For a system with $n$ qubits, the entire
readout error profile is specified by a $2^{n}\times 2^{n}$ matrix. Recent
proposals to use sub-exponential approximations rely on small and/or short-
ranged error correlations. In this paper, we introduce and demonstrate a
methodology to categorize and quantify multiqubit readout error correlations.
Two distinct types of error correlations are considered: sensitivity of the
measurement of a given qubit to the state of nearby “spectator” qubits, and
measurement operator covariances. We deploy this methodology on IBMQ quantum
computers, finding that error correlations are indeed small compared to the
single-qubit readout errors on IBMQ Melbourne (15 qubits) and IBMQ Manhattan
(65 qubits), but that correlations on IBMQ Melbourne are long-ranged and do
not decay with inter-qubit distance.

##  I Introduction

Quantum computers have the potential to provide an exponential speedup for a
variety of scientific and industrial applications. However, the present noisy
intermediate-scale quantum (NISQ) [1] computers introduce significant errors
that must be mitigated to acquire useful output. These errors can be
categorized into three types: state preparation errors, gate errors, and
measurement errors. State preparation errors occur when a quantum computer is
initialized to the ground state, but some qubits are in an excited state. Gate
errors occur when unitary operations are applied to the computer, leaving the
qubits in a superposition of the desire state and noisy states. Measurement
errors can often dominate state-preparation and gate errors, partly because
the readout time is not much shorter than the decoherence time, so that
decoherence can occur during the measurement process. We note that in most
practical applications, it is not possible to disentangle state preparation
and measurement (SPAM) errors, so these will be considered together in this
work.

Error correction on a quantum computer is significantly different than on
classical computers because qubits cannot be copied (‘cloned’) [2, 3, 4]. The
analog of copying is embedding a logical qubit into an entangled state of
several physical qubits. Full quantum error correction using an entangling
strategy requires significant overhead in terms of additional qubits and
quantum gates. Therefore, fault tolerance is infeasible on NISQ hardware due
to the limited size and fidelity of near term qubit arrays. Instead, error
mitigation (and not correction) is the general approach to quantum errors in
the NISQ era.

A variety of methods have been proposed to mitigate SPAM errors [5, 6, 7, 8,
9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27].
The fundamental object in these schemes is the response matrix,
$R=\Pr(\text{measure state $i$}|\text{state is $j$})$. If a quantum computer
has $n$ qubits, then $R\in[0,1]^{n\times n}$. Constructing the full response
matrix requires an exponential number of measurements: each of the $2^{n}$
states is prepared and measured many times to quantify the migrations away
from the prepared state during the readout process. Many of the schemes
referenced above propose approximations to $R$ that only require polynomial
measurements. For example, one possibility is to assume that qubit measurement
errors are independent from each other [11]. Then, a user only needs to
prepare $2n$ states to measure $\Pr(\text{measure 0}|\text{state was 1})$ and
$\Pr(\text{measure 1}|\text{state was 0})$ for each qubit. In this work, we
will explore multiqubit readout errors in order to understand to what extent
schemes that ignore correlations are applicable to existing devices. Previous
work has reported multiqubit correlations [22, 20, 26, 27], but their size and
range have not been systematically investigated.

Our paper is organized as follows. Section II introduces our protocol for
quantifying SPAM errors. Experimental results are presented in Sec. III, and
the paper ends with our conclusions and outlook in Sec. IV.

##  II Methods

Let $E_{j}^{(i)}$ be the positive-operator-valued measure (POVM) element $j$
for qubit $i$ (in the ideal projective limit, $E_{i}=\ket{i}\bra{i}$). We
define symmetrized, per qubit readout errors $\epsilon$ as

$\displaystyle\epsilon_{i}=\frac{1}{2}\left(\langle
E_{1}^{i}\rangle_{\ket{0\cdots 0}}+\langle
E_{0}^{i}\rangle_{\textbf{X}_{i}\ket{0\cdots 0}}\right)\,,$ (1)

where $\langle\bullet\rangle_{\psi}$ represents the expectation value of
operator $\bullet$ for the state $\psi$ and $\textbf{X}_{i}$ is the NOT
operator acting on qubit $i$ (i.e. the Pauli operator $\sigma_{j}^{x}$). Our
goal is to investigate readout error correlations and compare their magnitude
to $\epsilon$. We investigate two families of $2$-qubit readout error
correlations. The first, which we call $A$-type correlators, are defined as

$\displaystyle A_{ij}=\langle E_{1}^{i}\rangle_{\ket{0\cdots 0}}-\langle
E_{1}^{i}\rangle_{{\bf X}_{j}\ket{0\cdots 0}}\,.$ (2)

This quantifies the dependence of the qubit $i$ readout error on the state of
a nearby “spectator” qubit $j$. The second family, which we call $C$-type
correlators, are measurement operator covariances

$\displaystyle C_{ij}=\langle E_{0}^{i}E_{0}^{j}\rangle_{\psi}-\langle
E_{0}^{i}\rangle_{\psi}\langle E_{0}^{j}\rangle_{\psi}\,,$ (3)

where $\psi$ is any state. In this paper, we use $\psi=\ket{0}^{\otimes n}$.
Computing $\epsilon,A$, and $C$ requires the preparation of $n+1$ states: the
ground state and then the $n$ states where each qubit is in the $1$ state and
every other qubit is in the zero state. These states are measured up to 820k
times to reduce the statistical noise. These correlators were measured
previously on Melbourne [22]. (However, our definition of $A_{ij}$ differs
from that of [22] by a sign.)

Figure 1: Histograms of the $\epsilon,A$, and $C$ values for the IBMQ
Melbourne computer (top) and the IBMQ Manhattan computer (bottom). Note that
the first bin does not include underflow.

##  III Results

We implement all of the circuit preparation and scheduling with IBM’s Qiskit
software [28] and use the IBMQ Melbourne computer (all 15 qubits) and the IBMQ
Manhattan computer (all 65 qubits). We use 81920 (819200) measurements for
each circuit on IBMQ Melbourne (Manhattan).

Figure 2: The minimum, first quartile, median, third quartile, and maximum
$|A_{ij}|$ in bins of the shortest connected path between qubits $i$ and $j$
for IBMQ Melbourne (top) and IBMQ Manhattan (bottom).

Histograms of the $\epsilon,A$, and $C$ values for these two computers are
presented in Fig. 1. The per-qubit readout errors $\epsilon_{i}$ range from 1%
to 10% in both machines, with systematically lower readout errors on IBMQ
Manhattan. The $A$ correlations are typically higher than the $C$
correlations, with a small fraction of $A$ errors reaching the 1-10% level on
IBMQ Manhattan.

To examine the spatial distribution of the dominant ($A$-type) correlations
across the devices, we correlate each measured $A_{ij}$ with the minimum
connected distance between qubits. We define this distance by computing the
number of qubits coupled by two-qubit gates on the IBMQ machines that are
required to connect two given qubits. In other words, we measure inter-qubit
distance by the minimum number of CNOT-active edges connecting qubits $i$ and
$j$. This distance is computed efficiencly using Dijkstra’s algorithm [29].
Figure 2 presents the average $A_{ij}$ in bins specifying the minimum
connected distance. Interestingly, there is nearly no correlation between the
size of the $A_{ij}$ and qubit-qubit distance for IBMQ Melbourne, while on
IBMQ Manhattan, the noisiest pair of qubits are also the ones that have the
shortest path between them. We interpret these data as showing that the
measurement error correlations on Melbourne, while typically smaller than %1
in magnitude, are long ranged, extending over the entire device. On Manhattan
the error correlations are larger but are short-ranged.

Finally, we discuss the role of sampling errors in our experiment. Figure 1
shows that the two-qubit correlators $A$ and $C$ take a wide range of values
on Melbourne and Manhattan. At the same time, the $A$ and $C$ values
themselves have statistical errors resulting from their estimation with a
finite number of measurement samples. The sampling errors therefore bound the
size of the smallest $A$ and $C$ values that are statistically meaningful.
Estimating the output probability $p_{x}$ for a single classical state
$x\in\\{0,1\\}^{n}$ by using $N$ measurement samples results in a standard
error for the noisy estimate $p_{x}^{\rm est}$ given by

$\sqrt{{\rm Var}(p_{x}^{\rm est})}=\sqrt{\frac{p_{x}(1-p_{x})}{N}},$ (4)

which is no larger than $(2\sqrt{N})^{-1}$. Each $\epsilon_{i}$ is measured by
combining two estimated probabilities, so its standard error is bounded by
$(\sqrt{2N})^{-1}$. Each $A_{ij}$ is measured by subtracting two estimated
probabilities, so its standard error is also upper bounded by
$(\sqrt{2N})^{-1}$. Each $C_{ij}$ is obtained from a two-qubit probability
distribution, so its standard error is bounded by $(2\sqrt{N})^{-1}$.
Therefore the bound $(\sqrt{2N})^{-1}$, which takes the value of $2.5\times
10^{-3}$ on Melbourne ($N\\!=\\!81920$) and $7.8\times 10^{-4}$ on Manhattan
($N\\!=\\!819200$), can be applied to all three measured quantities. This
means that the long-range correlations observed on Melbourne are somewhat
above the noise floor, whereas the long-range correlations on Manhattan are
consistent with statistical noise.

##  IV Conclusions

In this paper, we present a set of observables that can be used for
categorizing and quantifying the correlated measurement errors on near-term
quantum computers. In addition to single-qubit SPAM errors $\epsilon_{i}$, we
measured a family of two-qubit correlators $A_{ij}$ that quantify sensitivity
to spectator qubits, as well as POVM covariances $C_{ij}$. We find that the
$C$-type correlations are always subdominant to the per-qubit readout errors
on IBMQ Melbourne and Manhattan, while the $A$-type correlations can be as
large as the $\epsilon_{i}$ on IBMQ Manhattan, reaching several percent.
Furthermore, the $A$-type correlations are long-ranged on Melbourne and
apparently extend over the entire device, whereas on Manhattan they are short-
ranged and confined to neighboring qubits. This is good news for future
scalable measurement error mitigation as well as fault-tolerant quantum
computation, which both require error correlations to be bounded in space and
time.

## Code and Data

The code for this paper can be found at https://github.com/LBNL-HEP-
QIS/ReadoutErrors. Quantum computer data are available upon request.

###### Acknowledgements.

BN is grateful to C. Bauer, M. Freytsis, W. de Jong, and M. Urbanek for useful
comments on the manuscript. This work is supported by the U.S. Department of
Energy, Office of Science under contract DE-AC02-05CH11231. In particular,
support comes from Quantum Information Science Enabled Discovery (QuantISED)
for High Energy Physics (KA2401032) and the Office of Advanced Scientific
Computing Research (ASCR) through the Accelerated Research for Quantum
Computing Program. This research used resources of the Oak Ridge Leadership
Computing Facility, which is a DOE Office of Science User Facility supported
under Contract DE-AC05-00OR22725.

## References

  * Preskill [2018] J. Preskill, Quantum Computing in the NISQ era and beyond, Quantum 2, 79 (2018).
  * Park [1970] J. L. Park, The concept of transition in quantum mechanics, Found. Phys. 1, 23 (1970).
  * Wootters and Zurek [1982] W. K. Wootters and W. H. Zurek, A single quantum cannot be cloned, Nature 299, 802 (1982).
  * Dieks [1982] D. Dieks, Communication by EPR devices, Phys. Lett. A 92, 271 (1982).
  * Bialczak  _et al._ [2010] R. C. Bialczak, M. Ansmann, M. Hofheinz, E. Lucero, M. Neeley, A. D. O’Connell, D. Sank, H. Wang, J. Wenner, M. Steffen, A. N. Cleland, and J. M. Martinis, Quantum process tomography of a universal entangling gate implemented with Josephson phase qubits, Nature Physics 6, 409 (2010).
  * Neeley  _et al._ [2010] M. Neeley, R. C. Bialczak, M. Lenander, E. Lucero, M. Mariantoni, A. D. O’Connell, D. Sank, H. Wang, M. Weides, J. Wenner, Y. Yin, T. Yamamoto, A. N. Cleland, and J. M. Martinis, Generation of three-qubit entangled states using superconducting phase qubits, Nature 467, 570 (2010).
  * Dewes  _et al._ [2012] A. Dewes, F. R. Ong, V. Schmitt, R. Lauro, N. Boulant, P. Bertet, D. Vion, and D. Esteve, Characterization of a Two-Transmon Processor with Individual Single-Shot Qubit Readout, Physical Review Letters 108, 057002 (2012).
  * Magesan  _et al._ [2015] E. Magesan, J. M. Gambetta, A. Córcoles, and J. M. Chow, Machine Learning for Discriminating Quantum Measurement Trajectories and Improving Readout, Physical Review Letters 114, 200501 (2015).
  * Debnath  _et al._ [2016] S. Debnath, N. M. Linke, C. Figgatt, K. A. Landsman, K. Wright, and C. Monroe, Demonstration of a small programmable quantum computer with atomic qubits, Nature 536, 63 (2016).
  * Song  _et al._ [2017] C. Song, K. Xu, W. Liu, C.-p. Yang, S.-B. Zheng, H. Deng, Q. Xie, K. Huang, Q. Guo, L. Zhang, P. Zhang, D. Xu, D. Zheng, X. Zhu, H. Wang, Y.-A. Chen, C.-Y. Lu, S. Han, and J.-W. Pan, 10-Qubit Entanglement and Parallel Logic Operations with a Superconducting Circuit, Physical Review Letters 119, 180511 (2017).
  * Gong  _et al._ [2019] M. Gong, M.-C. Chen, Y. Zheng, S. Wang, C. Zha, H. Deng, Z. Yan, H. Rong, Y. Wu, S. Li, F. Chen, Y. Zhao, F. Liang, J. Lin, Y. Xu, C. Guo, L. Sun, A. D. Castellano, H. Wang, C. Peng, C.-Y. Lu, X. Zhu, and J.-W. Pan, Genuine 12-qubit entanglement on a superconducting quantum processor, Physical Review Letters 122, 110501 (2019), arXiv: 1811.02292.
  * Wei  _et al._ [2020] K. X. Wei, I. Lauer, S. Srinivasan, N. Sundaresan, D. T. McClure, D. Toyli, D. C. McKay, J. M. Gambetta, and S. Sheldon, Verifying Multipartite Entangled GHZ States via Multiple Quantum Coherences, Physical Review A 101, 032343 (2020), arXiv: 1905.05720.
  * Havlicek  _et al._ [2019] V. Havlicek, A. D. Córcoles, K. Temme, A. W. Harrow, A. Kandala, J. M. Chow, and J. M. Gambetta, Supervised learning with quantum enhanced feature spaces, Nature 567, 209 (2019), arXiv: 1804.11326.
  * Chen  _et al._ [2019] Y. Chen, M. Farahzad, S. Yoo, and T.-C. Wei, Detector Tomography on IBM 5-qubit Quantum Computers and Mitigation of Imperfect Measurement, Physical Review A 100, 052315 (2019), arXiv: 1904.11935.
  * Chen  _et al._ [2020] M.-C. Chen, M. Gong, X. Xu, X. Yuan, J.-W. Wang, C. Wang, C. Ying, J. Lin, Y. Xu, Y. Wu, and et al., Demonstration of adiabatic variational quantum computing with a superconducting quantum coprocessor, Physical Review Letters 125, 180501 (2020), arXiv: 1905.03150.
  * Maciejewski  _et al._ [2020] F. B. Maciejewski, Z. Zimborás, and M. Oszmaniec, Mitigation of readout noise in near-term quantum devices by classical post-processing based on detector tomography, Quantum 4, 257 (2020), arXiv: 1907.08518.
  * Urbanek  _et al._ [2020] M. Urbanek, B. Nachman, and W. A. de Jong, Quantum error detection improves accuracy of chemical calculations on a quantum computer, Physical Review A 102, 022427 (2020), arXiv: 1910.00129.
  * Nachman  _et al._ [2020] B. Nachman, M. Urbanek, W. A. de Jong, and C. W. Bauer, Unfolding Quantum Computer Readout Noise, arXiv:1910.01969 [physics, physics:quant-ph] (2020), arXiv: 1910.01969.
  * Hamilton and Pooser [2019] K. E. Hamilton and R. C. Pooser, Error-mitigated data-driven circuit learning on noisy quantum hardware, arXiv:1911.13289 [quant-ph] (2019), arXiv: 1911.13289.
  * Hamilton  _et al._ [2020] K. E. Hamilton, T. Kharazi, T. Morris, A. J. McCaskey, R. S. Bennink, and R. C. Pooser, Scalable quantum processor noise characterization (2020), arXiv: 2006.01805.
  * Karalekas  _et al._ [2020] P. J. Karalekas, N. A. Tezak, E. C. Peterson, C. A. Ryan, M. P. da Silva, and R. S. Smith, A quantum-classical cloud platform optimized for variational hybrid algorithms, Quantum Science and Technology 5, 024003 (2020), arXiv: 2001.04449.
  * Geller and Sun [2021] M. R. Geller and M. Sun, Toward efficient correction of multiqubit measurement errors: pair correlation method, Quantum Sci. Technol. 6, 025009 (2021).
  * Geller [2020] M. R. Geller, Rigorous measurement error correction, Quantum Science and Technology 5, 03LT01 (2020).
  * R. Hicks, C. Bauer, and B. Nachman [2021] R. Hicks, C. Bauer, and B. Nachman, Readout Rebalancing for Near Term Quantum Computers, Phys. Rev. A 103, 022407 (2021), arXiv:2010.07496 [quant-ph] .
  * Funcke, Lena and Hartung, Tobias and Jansen, Karl and Kühn, Stefan and Stornati, Paolo and Wang, Xiaoyang [2020] Funcke, Lena and Hartung, Tobias and Jansen, Karl and Kühn, Stefan and Stornati, Paolo and Wang, Xiaoyang, Measurement Error Mitigation in Quantum Computers Through Classical Bit-Flip Correction, (2020), arXiv:2007.03663 [quant-ph] .
  * [26] G. S. Barron and C. J. Wood, Measurement error mitigation for variational quantum algorithms, arXiv: 2010.08520.
  * [27] F. B. Maciejewski, F. Baccari, Z. Zimborás, and M. Oszmaniec, Modeling and mitigation of realistic readout noise with applications to the quantum approximate optimization algorithm, arXiv: 2101.02331.
  * IBM Research [2019] IBM Research, Qiskit, https://qiskit.org (2019).
  * Dijkstra [1959] E. W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik 1, 269–271 (1959).

##  Appendix A Full Matrix Information

The full $A_{ij}$ and minimum distance matrices for IBMQ Melbourne and
Manhattan are presented in Fig. 3 and 4, respectively. The correlation between
nearness and high errors in $A_{ij}$ for Manhattan from Fig. 2 can be observed
as a slightly off-diagonal blue stripe in Fig. 4.

Figure 3: The matrix $A_{ij}$ (top) and the minimum distance between qubits
(bottom) for the IBMQ Melbourne computer.

Figure 4: The matrix $A_{ij}$ (top) and the minimum distance between qubits
(bottom) for the IBMQ Manhattan computer.