Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing

David Eppstein; Michael T. Goodrich; Songyu Liu

REVIEW 3 major objections 4 minor 21 references

Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing

T0 review · 3 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that the classic Cuthill–McKee heuristic is a polylogarithmic approximation for reordering bounded-bandwidth symmetric matrices, by introducing a new width parameter, BFS width, and showing that bandwidth and BFS width…

desk verdict The BFS-width parameter and the first Cuthill-McKee guarantees are real contributions; the main theorems are plausible, though Section 4 needs tightening and Theorem 10 is only a sketch. read the letter →

arxiv 2505.10789 v3 pith:DTM7XDXZ submitted 2025-05-16 cs.DS

David Eppstein , Michael T. Goodrich , Songyu Liu This is my paper · ORCID

classification cs.DS

keywords graphbandwidthBFSwidthCuthill-McKeealgorithmmatrixreorderingreconstructiondistanceoraclearcdiagramsparameters

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper sets out to give the first deterministic worst-case guarantees for the Cuthill–McKee and reverse Cuthill–McKee matrix-reordering heuristics, which are widely used but had no such analysis. To do this it introduces a new graph width parameter, BFS width, defined as the largest number of vertices at any single distance from any starting vertex. The central result is that graphs of bounded bandwidth have polylogarithmic BFS width, and that this is tight. From that, the paper derives that Cuthill–McKee reorders any bounded-bandwidth matrix to polylogarithmic bandwidth, that bounded-bandwidth graphs can be reconstructed from a distance oracle in near-linear queries, and that bounded-height arc diagrams can be redrawn at polylogarithmic height.

What carries the argument

The central object is BFS width: the maximum, over all choices of root vertex $v$ and all layers $i$, of the number of vertices at distance exactly $i$ from $v$ in a breadth-first search tree. The lower-bound construction uses level-$k$ trees, built inductively by attaching level-$(k-1)$ trees of geometrically increasing heights along a spine path and interleaving spine vertices with subtree vertices to keep bandwidth bounded while forcing a wide BFS layer. The upper-bound proof works by reducing to a BFS tree, deleting non-tree edges and all vertices below the first widest layer, and flipping subtrees so the extreme points of the bandwidth-minimizing layout become leaves; it then identifies left and right spines, shows that only $O(\log n)$ subtrees can reach the widest layer, and proves that removing the spine from a bandwidth-$k$ tree leaves forests of bandwidth at most $k-1$, allowing strong induction.

What would settle it

To falsify Theorem 14, exhibit an $n$-vertex graph $G$ with $\mathit{bw}(G) = k$ whose widest BFS layer, over every root, has size growing faster than $\log^{k-1} n$; for the base case, a bandwidth-2 graph whose BFS layers from every root contain a positive fraction of the vertices would contradict the claimed $O(\log n)$ bound for $k=2$.

Watch

Extended reading notes

Core claim

The paper's central discovery is a new width parameter, BFS width, together with a tight polylogarithmic relation to bandwidth. For every fixed $k \geq 1$, every $n$-vertex graph with bandwidth $k$ has BFS width $O(\log^{k-1} n)$, and there are level-$k$ trees with bandwidth $O_k(1)$ whose BFS width is $\Omega(\log^{k-1} n)$. Because the Cuthill–McKee and reverse Cuthill–McKee algorithms produce layouts whose bandwidth is $\Theta(\mathit{bfsw}(G,v))$ for the chosen root $v$, this relation makes the heuristics polylogarithmic approximations on bounded-bandwidth graphs, with matching lower bounds showing that a polylogarithmic dependence is necessary. The same BFS-width bound yields a deterministic $O(nB)$-query reconstruction algorithm for graphs of BFS width $B$, hence $\tilde{O}(n)$-query reconstruction for bounded-bandwidth graphs, and a construction of arc diagrams of polylogarithmic height for graphs that admit arc diagrams of bounded height.

Load-bearing premise

The upper-bound proof assumes, without a formal proof, that deleting non-tree edges and all vertices below the first widest BFS layer, and flipping subtrees so the extreme points of the bandwidth-minimizing layout become leaves, can be done without increasing bandwidth or decreasing the true BFS width; if any of these reductions fails, Theorem 14 would not follow.

Editorial extensions

If this is right

For any fixed bandwidth bound $b$, every $n \times n$ symmetric matrix that can be reordered to bandwidth at most $b$ is reordered by Cuthill–McKee and reverse Cuthill–McKee to bandwidth $O(\log^{f(b)} n)$, without the algorithm needing to know $b$.
The polylogarithmic dependence is necessary: for every $k$ there are matrices of bounded optimal bandwidth for which both heuristics output bandwidth $\Omega(\log^k n)$.
Graphs of BFS width $B$ can be reconstructed deterministically from a distance oracle using $O(nB)$ queries, and bounded-bandwidth graphs are reconstructed in $\tilde{O}(n)$ queries with no separate bounded-degree assumption.
Any graph with an arc diagram of bounded height can be redrawn, by ordering vertices by BFS layer from an arbitrary root, with height $O(\operatorname{polylog} n)$.
Because bounded BFS width implies bounded bandwidth, pathwidth, and treewidth, and BFS width is computable in polynomial time, the new parameter makes fixed-parameter tractable algorithms available on a class where those other width parameters are hard to compute.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Since Theorem 15 ties the layout bandwidth to a single BFS root, trying all possible roots and keeping the best Cuthill–McKee layout would give bandwidth $O(\min_v \mathit{bfsw}(G,v))$, and the paper's own level-2 trees show this minimum can be exponentially smaller than the worst-case BFS width.
The geometric-spine construction used for the lower bound is a natural template that could yield polylogarithmic lower bounds for other breadth-first-based layout heuristics, such as degree-aware or spectral orderings, whenever they are forced to reproduce a wide BFS layer.
The reconstruction algorithm only queries pairs whose layer numbers differ by at most one, so the same $O(nB)$ argument applies to any graph class whose BFS layers from a fixed root are small, suggesting a unified query bound for classes such as bounded-degree graphs with bounded diameter growth.
A testable extension would be to check whether the exponent $f(b)$ in the upper bound can be replaced by $O(\log b)$ when the root is chosen to minimize BFS width, since the min-width construction in Theorem 10 uses doubled copies that may not be worst-case for Cuthill–McKee as usually run.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should read this one. The paper introduces BFS width, a new width parameter that is polynomial-time computable, and proves that it is polylogarithmically tied to bandwidth. That alone is worth something. The first deterministic worst-case analysis of Cuthill-McKee follows cleanly from the upper bound, and the reconstruction algorithm is a simple and elegant BFS-layer scheme with near-linear query complexity. The level-tree lower bound construction is also nice and shows the polylog dependence is necessary.

The central argument seems sound to me. The stress-test note about the wlog flip in Section 4 does not hold up. The operation is a reflection of a subtree through the root (or through the parent vertex), not a rearrangement that moves a vertex far away. In a BFS tree, a subtree attaches through a single edge to its parent, and reflection preserves the length of that edge and all internal edge lengths. So the bandwidth does not increase. The counterexample in the note uses a layout where the flipped subtree is not actually reflected; it places vertices in a way the paper never describes.

The real soft spots are where the paper is too terse. Theorem 10, the lower bound on minimum BFS width, is essentially a paragraph sketch and should be expanded. Section 4's reductions—deleting vertices below the first widest layer, rerooting past degree-one roots, and flipping subtrees—are plausible but not formally proven; Lemma 13 in particular reads as an outline. These are fixable, and I do not think any of them is a load-bearing flaw, but a referee should ask for full details.

The reconstruction result is a straightforward application of the BFS-width definition and seems correct. The graph drawing application is minor, as the paper itself suggests. Citation pattern is fine; the related work on reconstruction and bandwidth approximation is covered.

Who is this for? People working on graph width parameters, matrix reordering heuristics, or distance-query reconstruction will get something out of it. I would bring it to a reading group and would cite it. It deserves a serious referee, and the right verdict is probably conditional acceptance: ask for a full proof of Theorem 10 and a rigorous treatment of the reductions in Section 4.

Referee Report

3 major / 4 minor

Summary. The paper introduces a new graph parameter, BFS width (bfsw), defined as the maximum number of vertices in any layer of a breadth-first search layering over all choices of the root, and its minimum variant bfswmin. The central claims are: (i) graphs of bounded bandwidth have BFS width that is both upper bounded and, for infinitely many graphs, lower bounded by polylogarithmic functions of n; (ii) these bounds imply first worst-case approximation guarantees for the Cuthill-McKee and reverse Cuthill-McKee heuristic on matrices of bounded optimal bandwidth; (iii) graphs of bounded bandwidth or bounded BFS width can be reconstructed deterministically with O(nB) distance queries; and (iv) bounded-height arc diagrams can be converted to polylogarithmic-height arc diagrams. The main technical results are Theorem 9 (lower bound on BFS width for bounded-bandwidth trees), Theorem 10 (lower bound on minimum BFS width), Theorem 14 (upper bound on BFS width for bounded-bandwidth graphs), and Theorem 15 (relation between CM/RCM bandwidth and BFS width).

Significance. If fully established, these results would be a genuine contribution: they give the first deterministic worst-case guarantees for a classic and widely used heuristic, introduce a width parameter that is polynomial-time computable unlike bandwidth and treewidth, and provide a very simple near-linear reconstruction algorithm for bounded-bandwidth graphs. The paper is self-contained in its definitions, and the lower-bound construction in Section 3 is explicit and checkable. The reconstruction algorithm is clean and its query bound is convincing. The main theorems are plausible, and the overall strategy, based on spine decomposition and induction on bandwidth, is natural. However, the current manuscript leaves several load-bearing proof obligations incomplete or internally inconsistent, so the results are not yet in a publishable state.

major comments (3)

[Section 3, Theorem 9] The statement of Theorem 9 says that for a level-k tree, bfsw(T) = Ω(log^k n), but the proof establishes a different exponent. For the level-2 tree the proof gives width w = j+2 with n = 3h = 3·2^j, hence bfsw(T) = Ω(log n), not Ω(log^2 n). For general level k the proof computes w_{k,j} = Ω(j^{k-1}) and n_{k,j} = Θ(2^j), giving Ω(log^{k-1} n). Moreover, for k=1 the level-1 tree is a path with bfsw(T)=2, contradicting the stated Ω(log n). The theorem statement and the level indexing must be reconciled; this off-by-one also affects the exponents claimed in Theorems 10 and 17.
[Section 3, Theorem 10] Theorem 10 is proved in one sentence: "A construction similar to Figure 5 can be used... Taking two reflected copies... gives a lower bound for minimum BFS width." This is not adequate for a load-bearing lower bound. To lower-bound bfswmin one must argue that for every possible root, some BFS layer is large, and the two-copy construction requires a precise accounting of how layers from an arbitrary root in one copy interact with vertices in the reflected copy. The constants and the placement of the root must also be checked. Since Theorem 17 depends on this lower bound, the proof needs to be written out in full.
[Section 4, Theorem 14] The proof of the main upper bound is a sketch rather than a complete induction. The "without loss of generality" reductions are asserted without formal proof. In particular, the claim that flipping a subtree around the root does not increase bandwidth is ambiguous: if "flip" means reversing the order of that subtree and placing it on the left of the root, the operation can increase the distance from the root to that child, whereas if it means reflecting the subtree across the root so that all edge lengths are preserved, the claim is true. The manuscript must specify the operation precisely and prove bandwidth monotonicity. The final induction step is also omitted: after Lemma 13, one must show explicitly that the O(log n) spine subtrees, each of bandwidth at most k-1 after spine removal, contribute O(log^k n) to the width of the widest layer of the original BFS tree, including the forest components created by deleting spine vertices. Lemma 13's argument that every saturated edge of a subtree contains a spine vertex inside it should be expanded into a rigorous position-based argument as well. These details are the load-bearing step for Theorems 16, 18, and 20.

minor comments (4)

[Abstract and Section 1] The name "Cuthull-McKee" is misspelled; it should be "Cuthill-McKee".
[Section 3] Theorem 9 says "for each non-negative integer k", but the level-k construction is defined only for k >= 1, and the formulas involving h_{k-1,i} = 2^i + k - 3 only make sense for k >= 2. Please state the valid range of k explicitly.
[Section 5.1, Theorem 15] The proof of the lower bound in Theorem 15 depends on which vertex of the widest BFS layer the Cuthill-McKee algorithm places farthest from the previous layer. Since the algorithm's within-layer ordering is not specified, the theorem should state explicitly which tie-breaking rule is assumed, or the proof should be phrased so that it holds for every within-layer ordering.
[Section 4, Lemma 12] The proof of Lemma 12 should state explicitly that v1 and v2 are the leftmost and rightmost vertices of the entire linear layout, not merely of the subtrees in S_i; this is implicit in the current text and should be made precise.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular reasoning identified; the BFS-width/bandwidth bounds are derived from independent graph-theoretic arguments.

full rationale

The paper's central derivation is self-contained. BFS width (Definition 1) is defined independently of bandwidth, and the paper then proves from scratch the relationships it uses: Theorem 5 derives bandwidth from minimum BFS width using the layer-difference property of BFS trees; Theorem 9 constructs bounded-bandwidth trees with polylogarithmic BFS width; Theorem 14 gives the converse upper bound by strong induction on bandwidth, with Lemmas 12 and 13 addressing subtree counts and bandwidth reductions; and Theorem 15 proves that Cuthill–McKee and reverse Cuthill–McKee layouts have bandwidth Theta(bfsw(G,v)) by giving explicit lower and upper bounds based on layer sizes, rather than assuming that equivalence. The applications in Theorems 16, 18, and 20 then combine these proven bounds without assuming their conclusions. The paper's citations of standard BFS properties in textbooks are not load-bearing in a self-referential way, and no fitted parameter is renamed as a prediction. To the extent that the wlog reductions in Section 4 may hide a correctness gap, that is an issue of proof validity, not circularity: the claimed bound does not reduce by construction to an input parameter or to a prior result authored by the same group.

Assumptions & free parameters 0 free parameters · 3 assumptions · 1 invented entities

The central claims rest on standard graph-theoretic facts (BFS layer property, bandwidth lower bounds from the literature) and on combinatorial identities; no fitted constants or ad hoc domain assumptions are introduced. The only new object, BFS width, is a formal definition rather than a postulated entity.

assumptions (3)

standard math In a BFS tree, every non-tree edge connects vertices whose layer numbers differ by at most 1.
Used in Theorem 5 and in the correctness of the reconstruction algorithm; a standard property of BFS layering.
domain assumption The degree lower bound bw(G) >= ceil(Delta/2) and the local density lower bound bw(G) >= D(G), due to Bottcher et al. and Gupta.
Used in Theorem 7 to show the example graph has bandwidth Omega(sqrt(n)); these are established results in the graph bandwidth literature.
standard math Faulhaber's formula for sums of powers, used to compute the number of vertices in level-k trees.
Used in the proof of Theorem 9 for the asymptotic counts n_{k,j} and widths w_{k,j}.

invented entities (1)

BFS width (bfsw) and minimum BFS width (bfsw_min) independent evidence
purpose: A new graph width parameter measuring the maximum size of a layer in a breadth-first layering, used to relate bandwidth to BFS structure and to design algorithms.
The parameter is well-defined in terms of graph distances, computable in polynomial time, and the paper proves formal upper and lower bounds relating it to bandwidth; it is a mathematical object rather than a postulated physical entity.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing." pith.science (2026). https://pith.science/paper/DTM7XDXZ

@misc{pith2026250510789,
  author       = {Pith},
  title        = {Pith review of: Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DTM7XDXZ}},
  note         = {Machine review of arXiv:2505.10789}
}

read the original abstract

We provide the first approximation quality guarantees for the Cuthull-McKee heuristic for reordering symmetric matrices to have low bandwidth, and we provide an algorithm for reconstructing bounded-bandwidth graphs from distance oracles with near-linear query complexity. To prove these results we introduce a new width parameter, BFS width, and we prove polylogarithmic upper and lower bounds on the BFS width of graphs of bounded bandwidth. Unlike other width parameters, such as bandwidth, pathwidth, and treewidth, BFS width can easily be computed in polynomial time. Bounded BFS width implies bounded bandwidth, pathwidth, and treewidth, which in turn imply fixed-parameter tractable algorithms for many problems that are NP-hard for general graphs. In addition to their applications to matrix ordering, we also provide applications of BFS width to graph reconstruction, to reconstruct graphs from distance queries, and graph drawing, to construct arc diagrams of small height.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 12 canonical work pages

[1]

Goodrich, Pedro Matias, and Martha C

1 Ramtin Afshar, Michael T. Goodrich, Pedro Matias, and Martha C. Osegueda. Mapping networks via parallel kth-hop traceroute queries. In Petra Berenbrink and Benjamin Monmege, 16 Bandwidth vs BFS Width editors, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), volume 219 ofLeibniz International Proceedings in Informatic...

work page 2022
[3]

ISSN: 1868-8969

Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISSN: 1868-8969. doi:10.4230/LIPIcs.SEA.2022.9. 3 Mugurel Ionut Andreica. A dynamic programming framework for combinatorial optimization problems ongraphs withbounded pathwidth,

work page doi:10.4230/lipics.sea.2022.9 2022
[9]

Cuthill and J

13 E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices. InProceedings of the 1969 24th national conference, ACM ’69, pages 157–172, New York, NY, USA, aug

work page 1969
[12]

24 Anupam Gupta

doi:10.4310/JOC.2012.v3.n4.a5. 24 Anupam Gupta. Improved bandwidth approximation for trees and chordal graphs.Journal of Algorithms, 40(1):24–36, jul 2001.doi:10.1006/jagm.2000.1118. 25 Eitan M. Gurari and Ivan Hal Sudborough. Improved dynamic programming algorithms for bandwidth minimization and the MINCUT linear arrangement problem.Journal of Algorithms...

work page arXiv 2012
[18]

ISSN: 1868-8969

Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISSN: 1868-8969. doi:10.4230/LIPIcs.ESA.2021.68. 33 Andrzej Proskurowski and Jan Arne Telle. Classes of graphs with restricted interval models. Discrete Mathematics & Theoretical Computer Science, 3(4):167–176,

work page doi:10.4230/lipics.esa.2021.68 2021
[21]

doi:10.1109/INFVIS.2002.1173155

ISSN: 1522-404X. doi:10.1109/INFVIS.2002.1173155

arXiv 2002
[1969]

14 Alberto Debiasi, Bruno Simoes, and Raffaele De Amicis

Association for Computing Machinery.doi:10.1145/800195.805928. 14 Alberto Debiasi, Bruno Simoes, and Raffaele De Amicis. Schematization of node-link dia- grams and drawing techniques for geo-referenced networks. InInternational Conference on Cyberworlds (CW), pages 34–41, 2015.doi:10.1109/CW.2015.68. 15 Chandan Dubey, Uriel Feige, and Walter Unger. Hardne...

arXiv
[1973]

27 Sampath Kannan, Claire Mathieu, and Hang Zhou

doi:10.1016/0012-365X(73)90067-8. 27 Sampath Kannan, Claire Mathieu, and Hang Zhou. Graph reconstruction and verification. ACM Transactions on Algorithms, 14(4):40:1–40:30, aug 2018.doi:10.1145/3199606. 28 Haim Kaplan and Ron Shamir. Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques.SIAM J. Comput., 25(3):540–561,

work page doi:10.1016/0012-365x(73)90067-8 2018

Show all 21 references

[1984]

26 Frank Harary and Allen J

doi:10.1016/0196-6774(84)90006-3. 26 Frank Harary and Allen J. Schwenk. The number of caterpillars.Discrete Mathematics, 6(4):359–365,

doi
[1990]

32 Claire Mathieu and Hang Zhou

doi:10.1109/12.46286. 32 Claire Mathieu and Hang Zhou. A simple algorithm for graph reconstruction. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors,29th Annual European Symposium on Algorithms (ESA 2021), volume 204 ofLeibniz International Proceedings in Informatics...

2021 doi
[1993]

30 Ales Komarek, Jakub Pavlik, and Vladimir Sobeslav

doi:10.2307/2152953. 30 Ales Komarek, Jakub Pavlik, and Vladimir Sobeslav. Network visualization survey. In Manuel Núñez, Ngoc Thanh Nguyen, David Camacho, and Bogdan Trawiński, editors,Computational Collective Intelligence: 7th International Conference, ICCCI 2015, Madrid, Sp...

doi
[1995]

7 Hans L

doi:10.1006/jagm.1995.1009. 7 Hans L. Bodlaender and Ton Kloks. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. Journal of Algorithms, 21(2):358–402,

1995
[1996]

1996.0049

doi:10.1006/jagm. 1996.0049. 8 Hans L. Bodlaender and Arie M. C. A. Koster. Combinatorial optimization on graphs of bounded treewidth. The Computer Journal, 51(3):255–269, may 2008.doi:10.1093/comjnl/ bxm037. 9 Michael Burch, Kiet Bennema Ten Brinke, Adrien Castella, Ghassen K...

1996
[1999]

34 Ilya Safro, Dorit Ron, and Achi Brandt

doi:10.46298/ dmtcs.263. 34 Ilya Safro, Dorit Ron, and Achi Brandt. Multilevel algorithms for linear ordering problems. ACM J. Exp. Algorithmics, 13:Article 1.4, 2009.doi:10.1145/1412228.1412232. 35 Jonathan S. Turner. On the probable performance of heuristics for bandwidth mi...

2009
[2001]

sentenceCase:1.doi:10.1007/3-540-44666-4_26

Springer. sentenceCase:1.doi:10.1007/3-540-44666-4_26. 17 Sherif El-Basil. Applications of caterpillar trees in chemistry and physics.Journal of Mathe- matical Chemistry, 1(2):153–174, July 1987.doi:10.1007/BF01205666. 18 Uriel Feige. Coping with the NP-hardness of the graph b...

1987
[2002]

INFOVIS 2002., pages 110–116, oct

2002
[2012]

4 Paul Bastide and Carla Groenland

URL:https://arxiv.org/abs/0806.0840, arXiv:0806.0840. 4 Paul Bastide and Carla Groenland. Optimal distance query reconstruction for graphs without long induced cycles, oct

arXiv
[2015]

Springer.doi:10.1007/978-3-319-24306-1_27. 31 S. Masuda, K. Nakajima, T. Kashiwabara, and T. Fujisawa. Crossing minimization in linear embeddings of graphs. IEEE Transactions on Computers, 39(1):124–127, jan

doi
[2021]

10 JuliaBöttcher, KlaasP.Pruessmann, AnuschTaraz, andAndreasWürfl

doi:10.1186/s42492-021-00088-8. 10 JuliaBöttcher, KlaasP.Pruessmann, AnuschTaraz, andAndreasWürfl. Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs. European Journal of Combinatorics, 31(5):1217–1227, jul 2010.doi:10.1016/j.ejc.2009.10.010...

doi
[2022]

ISSN: 1868-8969

Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISSN: 1868-8969. doi:10.4230/LIPIcs.STACS.2022.4. 2 Ramtin Afshar, Michael T. Goodrich, and Evrim Ozel. Efficient exact learning algorithms for road networks and other graphs with bounded clustering degrees. In Christian Schul...

2022 doi
[2024]

URL: http://arxiv.org/abs/2306

arXiv:2306.05979 [cs]. URL: http://arxiv.org/abs/2306. 05979, doi:10.48550/arXiv.2306.05979. 5 Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tollis.Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall,

doi arXiv

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [1]

Goodrich, Pedro Matias, and Martha C

1 Ramtin Afshar, Michael T. Goodrich, Pedro Matias, and Martha C. Osegueda. Mapping networks via parallel kth-hop traceroute queries. In Petra Berenbrink and Benjamin Monmege, 16 Bandwidth vs BFS Width editors, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), volume 219 ofLeibniz International Proceedings in Informatic...

work page 2022

[2] [3]

ISSN: 1868-8969

Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISSN: 1868-8969. doi:10.4230/LIPIcs.SEA.2022.9. 3 Mugurel Ionut Andreica. A dynamic programming framework for combinatorial optimization problems ongraphs withbounded pathwidth,

work page doi:10.4230/lipics.sea.2022.9 2022

[3] [9]

Cuthill and J

13 E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices. InProceedings of the 1969 24th national conference, ACM ’69, pages 157–172, New York, NY, USA, aug

work page 1969

[4] [12]

24 Anupam Gupta

doi:10.4310/JOC.2012.v3.n4.a5. 24 Anupam Gupta. Improved bandwidth approximation for trees and chordal graphs.Journal of Algorithms, 40(1):24–36, jul 2001.doi:10.1006/jagm.2000.1118. 25 Eitan M. Gurari and Ivan Hal Sudborough. Improved dynamic programming algorithms for bandwidth minimization and the MINCUT linear arrangement problem.Journal of Algorithms...

work page arXiv 2012

[5] [18]

ISSN: 1868-8969

Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISSN: 1868-8969. doi:10.4230/LIPIcs.ESA.2021.68. 33 Andrzej Proskurowski and Jan Arne Telle. Classes of graphs with restricted interval models. Discrete Mathematics & Theoretical Computer Science, 3(4):167–176,

work page doi:10.4230/lipics.esa.2021.68 2021

[6] [21]

doi:10.1109/INFVIS.2002.1173155

ISSN: 1522-404X. doi:10.1109/INFVIS.2002.1173155

arXiv 2002

[7] [1969]

14 Alberto Debiasi, Bruno Simoes, and Raffaele De Amicis

Association for Computing Machinery.doi:10.1145/800195.805928. 14 Alberto Debiasi, Bruno Simoes, and Raffaele De Amicis. Schematization of node-link dia- grams and drawing techniques for geo-referenced networks. InInternational Conference on Cyberworlds (CW), pages 34–41, 2015.doi:10.1109/CW.2015.68. 15 Chandan Dubey, Uriel Feige, and Walter Unger. Hardne...

arXiv

[8] [1973]

27 Sampath Kannan, Claire Mathieu, and Hang Zhou

doi:10.1016/0012-365X(73)90067-8. 27 Sampath Kannan, Claire Mathieu, and Hang Zhou. Graph reconstruction and verification. ACM Transactions on Algorithms, 14(4):40:1–40:30, aug 2018.doi:10.1145/3199606. 28 Haim Kaplan and Ron Shamir. Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques.SIAM J. Comput., 25(3):540–561,

work page doi:10.1016/0012-365x(73)90067-8 2018