Polynomial Bounds for the Grid-Minor Theorem

1 Introduction

• Before this work, proving a polynomial relationship between treewidth and largest grid-minor size remained an important open problem.The cited prior upper bound is f(k) = O(√(k/log k)).Source: §1 · pp. 1–2
• Theorem 1.1 gives every graph of treewidth k a grid minor of polynomial size, with exponent δ at least 1/98.The paper also gives a randomized algorithm that outputs a model of the grid minor with high probability in time polynomial in |V(G)| and k.Source: §1 · p. 2
• If G excludes a simple planar graph H as a minor, its treewidth is O(|V(H)|^c) for a universal constant c.The corollary follows because every simple planar graph H is a minor of a grid of size O(|V(H)|).Source: §1 · p. 2
• The Grid-Minor Theorem has applications in graph theory, algorithms, and lower bounds, and the paper says its main theorem directly improves some application bounds.The authors anticipate further applications for the theorem and the tools developed in the paper.Source: §1 · p. 2
• The algorithm constructs a path-of-sets system of width and length w with high probability when w^c ≤ O(k/polylog(k)), for a fixed constant c.It builds a tree-of-sets system first, then constructs a path-of-sets system from it.Source: §1 · p. 3

2 Preliminaries

• Treewidth is defined by minimum-width tree-decompositions, while a grid minor is represented by connected, disjoint vertex models joined by paths.A (g × g)-grid has g rows and g columns.Source: §2 · p. 4

2.1 Flows and Cuts

• For edge- and vertex-capacitated flows, max-flow/min-cut characterizes disjoint paths under unit capacities, and a bipartite graph of maximum degree ∆ has a matching of size at least |E|/∆.The matching can be computed efficiently.Source: §2.1 · pp. 5–6

2.2 Sparsest Cut

• AARV gives an O(√log k)-approximation for terminal sparsest cut, and Φ_T(G) ≥ α guarantees equal-sized disjoint terminal sets can exchange one unit each at edge-congestion at most 1/α.Here k is the number of terminals.Source: §2.2 · p. 6

2.3 Linkedness and Well-Linkedness

• If T1 ∪ T2 is α-well-linked and each side is node-well-linked in a graph of maximum degree ∆, subsets T1′ and T2′ are linked when |T2′| ≤ α|T2|/(2∆).Edge-well-linkedness requires every vertex partition to have at least α times the smaller terminal count in crossing edges.Source: §2.3 · p. 7

2.4 Boosting Well-Linkedness

• Selecting one terminal from each disjoint tree-terminal set of size at least ceil(1/α) yields a 1/(c + 1)-well-linked subset when each graph edge belongs to at most c trees.The selected subset contains exactly one terminal from each set.Source: §2.4 · p. 8
• An efficient algorithm selects at least floor(|Ti|/(3ceil(1/α))) terminals from each group Ti so their union is 1/2-well-linked.The input is a connected graph with an α-well-linked terminal set partitioned into groups.Source: §2.4 · pp. 8, 10
• A polynomial-time algorithm extracts at least α·κ/(32∆^4βARV(κ)) terminals that are node-well-linked; the partitioned version also preserves linkedness and 1/2-well-linkedness properties.For a partition into sets Ti, the corollary selects at least ⌊α·|Ti|/(2^10∆^5βARV(κ))⌋ terminals from each set, with each selected subset node-well-linked, their union 1/2-well-linked in G[Si], and distinct subsets linked in G.Source: §2.4 · p. 10

2.5 Treewidth and Well-Linkedness

• If k is the largest node-well-linked set size, then k^4 − 1 ≤ tw(G) ≤ k − 1; constructively, treewidth k yields an even Ω(k)-vertex set that is Ω(1/log k)-well-linked.For every equal-sized partition of that set, paths pair the two parts while each graph vertex belongs to at most 1/α* paths.Source: §2.5 · pp. 10–11

2.6 A Tree with Many Leaves or a Long 2-Path

• Given a connected graph and integers L and p satisfying the theorem’s condition, an efficient algorithm finds either a spanning tree with at least L leaves or a 2-path with at least p vertices.A 2-path is a path whose vertices each have degree 2 in the graph.Source: §2.6 · p. 11

2.7 Re-Routing Two Sets of Disjoint Paths

• Given ℓ1 > ℓ2 nearly disjoint path sets to s from U1 and U2, an efficient algorithm constructs ℓ1 nearly disjoint paths from U1 ∪ U2, retaining ℓ2 paths originating in U2.The resulting paths may share s but are otherwise vertex-disjoint.Source: §2.7 · p. 11

2.8 Cut-Matching Game and Degree Reduction

• The cut-matching game yields an Ω(log N)-expander after O(log^2 N) iterations with constant probability.In each iteration, the cut player bisects the vertex set and the matching player supplies a perfect matching across the cut.Source: §2.8 · p. 11

2.9 Starting Point

• With high probability, an efficient randomized algorithm finds a subgraph of maximum degree O(log^3 k) containing an Ω(k/poly log k)-vertex node-well-linked set.This provides the starting point for the algorithm on a graph of treewidth k.Source: §2.9 · p. 12

3 A Path-of-Sets System

• A path-of-sets system consists of disjoint connected vertex sets with linked endpoint sets and disjoint paths joining consecutive sets; it is strong when each endpoint set is node-well-linked.Each set contains disjoint A_i and B_i of size w, and the joining paths connect B_i to A_(i+1) directly.Source: §3 · p. 12
• Leaf and Seymour’s (w, ℓ)-grills and path-of-sets systems are roughly equivalent, but converting a grill can reduce its length to Ω(ℓ/w).A path-of-sets system yields a grill with the same parameters; a grill yields a path-of-sets system of width w and length Ω(ℓ/w).Source: §3 · p. 13
• Given linked sets A and B of size w, an efficient algorithm either finds an (h1 × h1)-grid minor or returns h2 disjoint A-to-B paths with pairwise connecting paths.The condition is (16h1 + 10)h2 ≤ w; each connecting path is internally disjoint from the returned paths.Source: §3 · p. 13
• For a path-of-sets system, an efficient algorithm either finds a grid minor or returns h2 disjoint paths traversing the sets in order, with connectors inside even-indexed sets.The paths cross each set along a path, and each connector is internally disjoint from the returned paths.Source: §3 · p. 13
• A system of width 16g^2 + 10g and length 2g(g − 1) yields an efficiently computable model of the (g × g)-grid minor.The construction applies to a path-of-sets system in G.Source: §3 · p. 13
• With high probability, an efficient randomized algorithm constructs a strong path-of-sets system of width w* and length ℓ* when k/log^c′ k > c′′w*(ℓ*)^48.The section states that choosing w*, ℓ* = Ω(k^1/49/polylog k) allows construction from a graph of treewidth k.Source: §3 · p. 13

4 Constructing a Path-of-Sets System

• A tree-of-sets system uses disjoint connected clusters as vertices of a degree-at-most-three tree, with w disjoint paths connecting clusters along each tree edge.Source: §4 · p. 14
• With Δ-bounded G, k node-well-linked degree-1 terminals, ℓ>1, w>4 log k, and k/log^4 k>cwℓ^19Δ^8, Theorem 4.1 outputs with high probability a tree-of-sets system avoiding T.The theorem strengthens.Source: §4 · p. 14
• Lemma 4.2 efficiently strengthens any tree-of-sets system; from a strong system with ℓ≥16w*(ℓ*)^2+1, Theorem 4.3 outputs a strong path-of-sets system of length ℓ* and width w*.Source: §4 · p. 15

4.1 Step 1

• Step 1 computes ⌊w̃/ℓ*⌋ paths from the root cluster to each selected leaf cluster, traversing exactly the clusters on their tree path in order.Source: §4.1 · p. 17

4.2 Step 2

• Step 2 processes the tree bottom-up, joining child path-of-sets systems to obtain a system of length ℓ* and width w*.The construction imitates a depth-first tour and relies on the paths built in Step 1.Source: §4.2 · pp. 18–19
• Rerouting 4w* disjoint Γ-to-Γ′ paths twice with Lemma 2.16 retains at least |P|-8w* and |P′|-8w* paths in disjoint families.The rerouted paths remain disjoint from the retained paths in both families.Source: §4.2 · p. 20
• At least w* rerouted paths join Γ2 to Γ′1; concatenating them with Q′ prefixes forms paths from Y1 to X2, disjoint from both systems except at endpoints.These paths provide the connectors for a new path-of-sets system with vertex sets L_S and end sets X1 and Y2.Source: §4.2 · p. 21
• The construction discards Q′ paths that meet the rerouted paths, at most 8w* paths, while the Q′ paths for Y2 remain disjoint from the new connectors.The text gives the resulting lower bound for |Q′_X1| in terms of the starting size and the number of iterations, though the formula is fragmented in the supplied passage.Source: §4.2 · p. 21
• The resulting path-of-sets system is strong because each participating boundary set δSi(e) is node-well-linked in G[Si].Each vi in L is incident with only one edge of T, and those boundary vertices are the only Si vertices that may participate in the system’s paths.Source: §4.2 · p. 21

5 Proof of Theorem 4.1

• The proof adapts by choosing parameters that make the number of clusters polynomial in k and by extending its arguments from edge to vertex connectivity.The authors also state that they simplify some of 's arguments.Source: §5 · p. 21

5.1 High-Level Overview

• The proof seeks ℓ disjoint subgraphs with well-linked vertex sets by finding ℓ² good routers that avoid terminals, satisfy a bandwidth condition, and send substantial flow to the terminals.A tree-of-sets system requires each constituent subgraph to contain a well-linked set; the proof divides into finding routers and constructing the system from them.Source: §5.1 · p. 22

From a Good Family of Routers to a Good Tree-of-Sets System

• From a good router family, the proof builds a tree-of-sets system in two phases, using path connections and a maximum-degree-3 spanning tree.The construction first connects routers and then uses splitting operations; a spanning tree of maximum degree 3 in the final auxiliary graph defines the system.Source: From a Good Family of Routers to a… · pp. 22–23

5.2 Vertex Clusterings and Legal Contracted Graphs

• A good clustering keeps each terminal in its own cluster and uses small clusters with the bandwidth property; contracting clusters yields a legal contracted graph.Clusters are classified by whether their boundary size is below or above w0; the contracted graph hides portions of the original graph inside clusters.Source: Finding a Good Family of Routers · p. 23, §5.2 · p. 26

Finding a Good Family of Routers

• The constructive proof identifies two algorithmic obstacles: finding a removable edge in a large cluster and finding a violating cut for bandwidth decomposition.The stated existence arguments do not provide efficient algorithms for either task, motivating the potential-function approach.Source: Finding a Good Family of Routers · p. 25
• The constructive search uses clustering and a decreasing potential to make progress until it finds a good tree-of-sets system.Each phase either finds the system or produces a clustering with potential lower by at least 1; the proof bounds the search by O(|E(G)|) phases and polynomially many iterations per phase.Source: Finding a Good Family of Routers · pp. 25–26

5.2 Vertex Clusterings and Legal Contracted Graphs

• The potential estimates cross-cluster edges within a factor of 1.1, and bandwidth decomposition partitions a connected small cluster into small bandwidth-property clusters without increasing potential.For the set E′ of edges between clusters, |E′| ≤ ϕ(C) ≤ 1.1|E′|.Source: §5.2 · pp. 27, 30
• PARTITION on a (w0, α)-violating cut and SEPARATE across a cut of size <w0/2 preserve acceptability, lower potential by at least 1/n, and keep new large clusters within old ones.SEPARATE lowers potential by at least 1, while PARTITION lowers it by more than 1/n.Source: §5.2 · pp. 28–30

5.3 The Algorithm

• Each phase outputs a good tree-of-sets system or, with high probability, a good clustering whose potential is at least 1 lower.Starting from singleton clusters, the algorithm repeats phases and terminates after O(|E(G)|) phases.Source: §5.3 · p. 30
• Each partition with the desired properties has, for every X_j, fewer than 10m/ell_0 boundary edges and at least m/(2ell_0^2) internal edges; retries obtain one with high probability after poly(n) iterations.Here m = |E(G′ \ T)| and m ≥ k/3.Source: §5.3 · pp. 30–31
• For each 1 ≤ j ≤ ℓ0, the constructed acceptable clustering Cj has potential at most ϕ(C) − 1.The construction adds clusters disjoint from X′j and connected components of G[X′j], applying bandwidth decomposition to any small components.Source: §5.3 · p. 32
• For disjoint terminal-avoiding sets S1,...,Sℓ0, Theorem 5.9’s efficient randomized algorithm finds with high probability a good tree-of-sets system or one of two partition outcomes.The alternatives are a (w0, α)-violating partition of some Sj, or a partition (A, B) with Sj ⊆ A, T ⊆ B, and |EG(A, B)| < w0/2.Source: §5.3 · pp. 32–33
• At most 1.1|E(G)|·n·ℓ0 iterations suffice to find a good clustering with lower potential or complete a successful iteration.Each unsuccessful iteration decreases one partition’s potential by at least 1/n through a SEPARATE or PARTITION operation.Source: §5.3 · p. 33

5.4 Proof of Theorem 5.9

• Theorem 5.10 constructs a terminal graph with edge groups of size at most κ and representative paths that are node-disjoint except at endpoints.Its paths avoid terminals internally, and each edge incident to a terminal occurs in at most two paths.Source: §5.4 · p. 34

5.4.1 Phase 1

• After contracting each cluster into a super-node, the algorithm applies Theorem 5.10 to H, its terminals, and µ; in Case 2, connected Z has a tree with at least ℓ leaves, so Phase 2 follows.Source: §5.4.1 · pp. 35–36
• In the long-path case, random group-edge selection and endpoint thinning build mutually disjoint path sets, after which bandwidth checks either certify the tree-of-sets system or return a violating cut.The algorithm tests each cluster’s bandwidth property with AARV.Source: §5.4.1 · p. 36
• With high probability, the algorithm either finds a (w0, α)-violating cut or produces cluster edge sets Ei and w3 node-disjoint direct paths between every pair, using an edge from each endpoint set.Each path starts and ends with an edge from the respective cluster’s set Ei or Ej.Source: §5.4.1 · pp. 36–37
• For each selected leaf cluster, a root-to-cluster flow is assembled along the tree; if an internal cluster lacks the needed flow, its minimum cut yields a violating cut.The concatenated flows are scaled so each selected cluster sends at least floor(w1α/(4ℓ∆^2)) flow units to the root cluster with vertex-congestion at most 1.Source: §5.4.1 · pp. 37–38
• Phase 1 finds ℓ disjoint sets with w3 outgoing edges each, joined pairwise by w3 node-disjoint direct paths.The paths use an edge from each set as their first and last edges.Source: §5.4.1 · p. 38

5.4.2 Phase 2

• Phase 2 replaces each set with a super-node and applies Theorem 5.10 to obtain degree and pairwise edge-connectivity exactly 2w3.This equal-degree, equal-connectivity property enables construction of the tree-of-sets system.Source: §5.4.2 · pp. 38–39

Observation 5.16

• Every vertex pair in ˜Z supports at least (1 −1/ℓ)h flow, enabling an efficient spanning tree of maximum degree 3 via Singh and Lau.The tree uses the capacity structure established by Observation 5.16.Source: Observation 5.16 · pp. 39–40
• With high probability, the tree edges receive w mutually node-disjoint paths, and AARV either certifies each set's αBW-bandwidth or finds a violating partition.The algorithm samples edges to form path sets, trims them to size w, and checks each set's interface using a sparsest-cut instance.Source: Observation 5.16 · pp. 40–41

Theorem 6.1

• Theorem 6.1 provides a strong path-of-sets system disjoint from the terminals, with bandwidth properties and bounded-congestion paths connecting every terminal to each set.The authors identify the result as potentially useful for approximation algorithms for maximum-throughput routing, including All-or-Nothing Flow and Disjoint Paths in node-capacitated graphs.Source: §6 · p. 41

Routing motivation

• The added terminal-to-interface paths address a crossbar-routing obstacle: connecting input pairs to the crossbar interface without adding congestion requires paths disjoint from the crossbar.Simply adding paths using terminal well-linkedness may alter set boundaries and destroy boundary well-linkedness.Source: §6 · p. 41

Theorem 6.2

• Theorem 6.2 computes a tree-of-sets system whose sets exclude terminals and satisfy the required bandwidth property, together with bounded-congestion paths from every terminal to each set.The theorem guarantees its output with high probability.Source: §6 · pp. 41–42

Theorem 6.3

• Theorem 6.3 either finds a violating partition, a sparse cut separating a set from the terminals, or a valid tree-of-sets output for Theorem 6.2.The algorithm returns one of these outcomes with high probability.Source: §6 · p. 43

Extensions

• Claim 6.6 gives an efficient algorithm that either certifies ˆRi is γ-well-linked in G[Si] or returns a (w0, α)-violating partition of Si.It uses AARV to approximately compute a sparsest cut; a cut below the stated threshold yields the violating partition.Source: §6 · p. 46
• The final step removes terminals T* from each cluster and adjusts paths so they still connect terminals to the resulting clusters with edge-congestion at most η*.The passages state that the modified tree-of-sets system remains valid and that each removed terminal is connected to its unique neighbor in the resulting cluster.Source: Step 3 · p. 47
• Claim 6.7 establishes that each resulting cluster is BW-well-linked, yielding the BW-bandwidth property in G*.The passage says this claim finishes the proof of Theorem 6.3.Source: Step 3 · p. 47

• The non-constructive proof is simpler and gives better parameters.Source: §A.1 · p. 51
• That proof can be turned into an algorithm running in poly(n)·2^κ time.Source: §A.1 · p. 51
• The constructive proof runs in poly(n, κ) time.Source: §A.1 · p. 51

A.1.1 A non-constructive proof

• A minimum-order balanced separation with respect to T has a separator X that is node-well-linked in Y.The proof establishes this by contradiction: a smaller separator between equal-sized subsets of X would yield a balanced separation of smaller order.Source: §A.1.1 · p. 51
• The proof starts from a balanced separation whose two sides each contain at least |T|/4 terminals.Source: §A.1.1 · p. 51
• A flow between terminal subsets is converted into disjoint paths and truncated at X, producing paths from terminals to vertices of X.The flow bound is converted to an integral path set, then each path is truncated at its first vertex in X.Source: §A.1.1 · p. 51
• The paths from terminal subsets are joined through X using its node-well-linkedness, yielding disjoint paths connecting the subsets.The proof combines the terminal-to-X paths with disjoint paths through Y and handles shared terminals separately.Source: §A.1.1 · p. 52

A.1.2 A Constructive Proof

• ⌈κα/(2∆²)⌉ node-disjoint paths can be found between the two terminal sides of any balanced partition.The path count follows by routing flow from the smaller terminal side and using integrality.Source: §A.1.2 · p. 52
• The algorithm finds a balanced partition with connected G[B] and ΓA(P) 1/βARV(κ)-well-linked in G[A].If the sparsest-cut step fails to certify well-linkedness, it refines the partition without increasing cut sparsity, then moves a connected side to strictly reduce the number of crossing edges.Source: §A.1.2 · pp. 52–54
• The path-grouping algorithm retains at least half of P in disjoint connected subgraphs, each containing between q and 4∆q paths.It contracts paths into supernodes and repeatedly extracts connected tree regions meeting the required path-count bounds.Source: §A.1.2 · pp. 54–55
• Selecting one terminal from each path group yields a set T′ that is node-well-linked in G.The proof routes flow from terminals through their groups to the well-linked special neighbors, then between those neighbors in G[A].Source: §A.1.2 · pp. 55–56

A.2 Proof of Theorem 2.15

• An edge joining three consecutive degree-2 vertices can replace a tree edge and make the middle vertex a new leaf.The exchange deletes (b, c) and adds (a, c).Source: §A.2 · p. 56
• Other edges incident to a degree-2 vertex enable exchanges that increase the leaf count by at least one.Depending on whether the added edge reaches outside or inside the vertex's subtree, the exchange removes one of two specified tree edges.Source: §A.2 · p. 56
• If no improvement step is possible, trimming two vertices from each end of a maximal tree 2-path leaves a 2-path in Z with at least p vertices.The tree has at most 2L maximal 2-paths, so one contains at least p + 4 vertices before trimming.Source: §A.2 · p. 56

A.3 Proof of Lemma 2.16

• The proof was suggested by Paul Seymour; Conforti, Hassin and Ravi give a different proof using stable matchings.Source: §A.3 · p. 56
• Edges outside E1 are deleted while ℓ2 nearly-disjoint U′2–s paths remain, leaving every retained non-E1 edge necessary for that property.The final graph preserves X1 while removing any eligible edge.Source: §A.3 · p. 57
• The target is ℓ1 nearly-disjoint paths, exactly ℓ2 of which originate in U′2.The paths start in U′1 ∪ U′2 and end at s.Source: §A.3 · p. 57
• A node-capacitated flow network encodes the required path origins, and an integral flow of value ℓ1 supplies the paths.The capacities of t1 and t2 allocate ℓ1 − ℓ2 and ℓ2 units to the two origin sets.Source: §A.3 · pp. 57–58

A.4 Proof of Theorem 2.18

• The cut-matching game builds an expander H on an Ω(k)-sized vertex set X, with embedding congestion O(log^3 k).Each game round routes a matching through paths in G; the union of these paths forms the embedded graph G′.Source: §A.4 · p. 58
• AARV accepts H when the cut sparsity reaches the stated threshold; after |X| executions, the algorithm succeeds with high probability.A low-sparsity outcome causes the current H to be discarded and the procedure repeated.Source: §A.4 · p. 58
• The construction extracts a subset X′ that is node-well-linked in G′.The proof uses the expander embedding and a bounded-degree subgraph to obtain the subset.Source: §A.4 · p. 58

B Proof of Theorem 3.1

• The linkage graph H(L) connects two path-vertices when a joining path in G has interior disjoint from the linkage, and H(L) is connected.An A-B linkage is a set of w disjoint paths connecting A to B.Source: B Proof of Theorem 3.1 · p. 58
• A good linkage is one whose corresponding graph has no 2-path with 8h1 + 1 or more vertices.The proof starts from an arbitrary A-B linkage and applies Theorem B.1 while the linkage is not good.Source: B Proof of Theorem 3.1 · p. 59
• A good linkage yields at least h2 node-disjoint A-B paths by selecting paths corresponding to leaves of a spanning tree.The spanning tree has at least w / (2(8h1 + 5)) leaves, which is at least h2.Source: B Proof of Theorem 3.1 · p. 59
• After O(w) iterations, the procedure either finds an h1 × h1 grid minor or reduces the linkage graph’s degree-2 vertices below 8h1 + 1.At each step, Theorem B.1 either returns a grid minor, a good linkage, or a linkage with fewer degree-2 vertices.Source: B Proof of Theorem 3.1 · p. 59

B.1 Proof of Theorem B.1

• A long 2-path supplies z disjoint A-B connectors, each classified as type 1 or type 2 by where it last meets the middle path groups.At least half are of one type, yielding at least h1 selected subpaths Q* for the subsequent simplification.Source: §B.1 · pp. 59–60
• Bump and cross reroutings either reduce degree-2 vertices in H(L) or preserve its structure while strictly decreasing the auxiliary graph’s edge count.The algorithm therefore terminates within O(|E(G)|) iterations unless it has already returned a linkage with fewer degree-2 vertices.Source: §B.1 · pp. 61–62
• If the auxiliary graph has no bump or cross, the trimmed union of linkage paths and selected connector segments is planar.The proof subdivides connector segments at their intersections with linkage paths; absent bumps, endpoints join consecutive paths, and absent crosses the resulting graph is planar.Source: §B.1 · pp. 62–63
• The proof removes hills by replacing connector segments with portions of linkage paths, then establishes the intersection pattern needed for grid extraction.The contradiction argument for Claim B.3 uses a different connector intersecting the replaced segment to obtain a path with a larger index.Source: §B.1 · p. 63
• Contracting each linkage-path intersection and suppressing degree-2 vertices in the resulting union yields an h1 × h1 grid minor.The construction then discards h1 extra rows.Source: §B.1 · p. 63

C Proof of Corollary 3.2

• Applying Theorem 3.1 to each even cluster either finds an h1 × h1 grid minor or supplies h2 node-disjoint paths.The paths connect selected subsets of the cluster’s A and B boundary sets, with internal connectors between every pair.Source: C Proof of Corollary 3.2 · p. 63
• Well-linkedness in odd clusters connects the path collections from neighboring even clusters into h2 disjoint paths spanning the cluster sequence.Each resulting path intersects each cluster in a path, in the order of the clusters.Source: C Proof of Corollary 3.2 · pp. 63–64
• For every even cluster, each pair of spanning paths has an internal connector in that cluster, disjoint from the spanning paths.The resulting paths are contained in G′.Source: C Proof of Corollary 3.2 · p. 64

C.1 Proof of Corollary 3.3

• G* contains a g × g grid as a minor, and the proof completes the argument by constructing a subdivision of G* in G.G* starts from a grid with g rows and g(g − 1) columns, retaining one vertical edge per column before deleting degree-1 vertices and suppressing degree-2 vertices.Source: §C.1 · p. 64
• The g spanning paths map to G*’s horizontal rows, while connectors in even clusters map to its vertical edges.Each vertical edge joins consecutive rows and is mapped to a path connecting the corresponding spanning paths.Source: §C.1 · p. 64
• Each horizontal edge maps to the segment of its row path between the mapped endpoints.This completes the edge mapping after the vertices and vertical edges have been mapped.Source: §C.1 · p. 64