Pith. sign in

REVIEW 1 major objections 4 minor 51 references

Shorter Labeling Schemes for Planar Graphs

T0 review · 1 major / 4 minor · reviewed 2026-08-14 · 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 every efficiently flat class of graphs—including planar graphs—admits an adjacency labeling scheme of length (4/3 + o(1)) log n bits, with polynomial-time encoding and constant-time decoding.

desk verdict Solid, real improvement to planar adjacency labels; the 4/3 log n bound is proved cleanly and the weak points are minor and repairable, so it deserves a proper referee despite being superseded. read the letter →

arxiv 1908.03341 v2 pith:W3CUPJTN submitted 2019-08-09 cs.DS

Marthe Bonamy (LaBRI) , Cyril Gavoille (LaBRI) , Michal Pilipczuk This is my paper · ORCID
classification cs.DS MSC 05C8568R1005C10
keywords adjacencylabelingschemesplanargraphsinduced-universalproductstructuretheoremtreewidthflatgraphclassesstrongofboundedEulergenus
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 is trying to establish that the adjacency relation of an n-vertex planar graph can be encoded in labels of about 1.33 log n bits per vertex, so that whether two vertices are adjacent can be read off from their two labels alone, without any global data structure. This improves the previous best bound of about 2 log n bits per vertex. The construction actually works for any 'efficiently flat' class of graphs—those that can be embedded, in polynomial time, into the strong product of a bounded-treewidth graph and a path—which includes planar graphs, graphs embeddable in a fixed surface, and k-planar graphs. If the claim is right, it also yields an explicit graph on $n^{{4/3+o(1)}}$ vertices containing every n-vertex planar graph as an induced subgraph, improving the previous $n^{{2+o(1)}}$ bound.

What carries the argument

The central object is the product structure theorem of Dujmović et al.: a planar graph G embeds as a subgraph of H ⊠ P, where ⊠ is the strong product, H has constant treewidth (at most 8 for planar graphs), and P is a path. The paper's new engine is a refined bidecomposition lemma (Lemma 5) that, for a bounded-treewidth graph, produces a decomposition in which a prescribed small set of vertices sits near the root, so those vertices can receive much shorter labels; this is proved with a two-weight balanced-separator argument. The lemma lets the scheme 'spend' short labels on the small border sets that appear when the path P is cut into width-d blocks, and choosing d = $n^{{1/3}}$ balances the two label costs at 4/3 log n.

What would settle it

Implement the scheme on the planar grid family with n = $k^{2}$ vertices and measure the maximum label length output by the encoder for k = 2^m, m up to about 30; the observed maximum should track (4/3) log n + O(log log n). A persistent divergence beyond the allowed second-order slack would refute the label-length claim, while a family of planar graphs requiring more than (4/3+o(1)) log n bits in any correct labeling scheme would refute the bound's optimality.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: every efficiently flat class of graphs admits a labeling scheme of length (4/3) log n + O(log log n), with the Encoder running in polynomial time and the Decoder in constant time. For planar graphs this gives labels of length (4/3+o(1)) log n, improving the previous (2+o(1)) log n bound, and an explicit induced-universal graph on $n^{{4/3+o(1)}}$ vertices. The scheme splits a product-structure embedding G ⊆ H ⊠ P into blocks of width d = $n^{{1/3}}$ along the path P, labels the resulting sparse border strips with short labels via a strengthened bounded-treewidth labeling, and labels the rest with an auxiliary scheme for short paths; balancing the two label costs at d = $n^{{1/3}}$ yields the 4/3 log n figure.

Load-bearing premise

The whole construction assumes the class is 'efficiently flat': every graph can be embedded, in polynomial time, into a strong product H ⊠ P with H of constant treewidth and P a path—a property external to this paper that is known to hold for planar graphs but must hold and be efficiently computable for every class the theorem is applied to.

Editorial extensions

If this is right

  • Planar adjacency labels drop from (2+o(1)) log n to (4/3+o(1)) log n bits per vertex, with a polynomial-time encoder and constant-time decoder.
  • There is an explicit induced-universal graph for n-vertex planar graphs on n^{4/3+o(1)} vertices, improving the previous n^{2+o(1)} bound.
  • The same 4/3 log n bound holds for every efficiently flat class: graphs embeddable in a fixed surface, k-planar graphs for fixed k, apex-minor-free classes, and other classes covered by the product structure theorem.
  • As a side result, planar graphs whose product-structure embedding uses a path of length d (e.g., bounded by diameter) admit labels of length log n + log d + O(log log n).
  • The dependence on the treewidth bound w is linear in the O(log log n) second-order term, so the construction remains efficient for any fixed w.

Reading between the lines

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

  • Going beyond the paper: the 4/3 constant is not obviously tied to planarity—it emerges purely from equating the two label costs on a path of width d, so any flat class with the same product structure would inherit the same constant; only the O(log log n) term would shift with the treewidth bound.
  • The refined bidecomposition lemma (Lemma 5) is a standalone tool: it shows how to compress labels of a prescribed small set in any bounded-treewidth graph, a property that could be reused in other labeling problems where a few vertices are known in advance and need extra-short labels.
  • The paper does not address lower bounds for constant-time decoding; nothing here rules out a (1+o(1)) log n scheme with constant-time decoding, so the 4/3 should be read as the best current construction within this framework, not a proven barrier.
  • A testable extension: apply the same border-saving bidecomposition to distance labeling or ancestry labeling on flat classes; the short-label-on-special-set trick may transfer to other informative labeling functions.
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.

Referee Report

1 major / 4 minor

Summary. The paper presents an adjacency labeling scheme for every efficiently flat class of graphs, in particular for planar graphs, using labels of length (4/3 + o(1)) log n. This improves the previous best known bound of (2 + o(1)) log n for planar graphs. The construction combines the product structure theorem, which embeds every graph from an efficiently flat class into H ⊠ P with H of bounded treewidth and P a path, with a strengthened bounded-treewidth labeling scheme, an auxiliary short-path labeling scheme, and a strip/border decomposition that isolates a small set of border vertices. The resulting labels support constant-time adjacency tests and polynomial-time encoding, and they yield an induced-universal graph for n-vertex planar graphs with n^{4/3+o(1)} vertices. The main theorem is explicitly conditional on the polynomial-time algorithmic version of flatness, which is supplied for planar graphs and other classes by the cited product structure theorem.

Significance. If the proof is completed, the result is a substantial improvement in planar graph labeling schemes and in the size of induced-universal graphs for planar graphs, and it extends uniformly to all efficiently flat classes, including graphs of bounded Euler genus and k-planar graphs. The paper's main technical contribution is the strengthened bounded-treewidth labeling scheme with property (P2), which assigns labels of length log q + O(log log n) to a prescribed set of q vertices, and the clean label-superposition argument that optimizes the tradeoff between log n + log d and 2 log(n/d). The manuscript also gives detailed proofs of the algorithmic claims and clearly records the dependence on the external product structure theorem. The announced subsequent work of Dujmović et al. achieves the optimal (1 + o(1)) log n for efficiently flat classes, so the novelty here now lies in the simpler proof and the constant-time decoder rather than in the 4/3 log n bound itself, which was best at the time of the conference version.

major comments (1)
  1. [Section 3, Claim 4 (proof)] The proof applies Claim 3 to the family Ω of connected components of H − X using the fact that each component C satisfies ω_t(C) ≤ ε ω_t(H). However, Claim 3 requires the stronger hypothesis ω_t(C) ≤ ε ω_t(Ω), and ω_t(Ω) can be much smaller than ω_t(H) when the separator X contains a large fraction of the weight. Thus the application is not licensed as written, and this is a genuine gap in the proof of Lemma 5, since Claim 4 is the mechanism that simultaneously halves the vertex count and the number of special vertices. The gap is repairable with a constant-factor adjustment: choose the separator parameter in Claim 2 to be Θ(ε); observe that if ω_t(Ω) ≤ (1/2 + ε)ω_t(H) then any bipartition of Ω is acceptable for that weight coordinate, while otherwise ω_t(Ω) is within a constant factor of ω_t(H) and Claim 3 can be applied with parameter O(ε). The constants in Claim 4 and in Lemma 5 should be restated accordingly. The final 4/3 log n bound is unaffected by this repair, but the proof should be corrected before publication.
minor comments (4)
  1. [Lemma 5, depth calculation] The displayed equality log(1/(1+2ε)) = log((1−2ε)/(1+2ε)) is incorrect; the left-hand side is larger than log(1−2ε). Since the argument only needs the lower bound log(1−2ε) > −4ε, the proof is easily corrected by replacing the equality with an inequality.
  2. [Claim 3, proof] In the definition of the index p, the sums are written with ω1(x_i) while the running index is x_j; in the final bound, the strict inequality '2ε > |...|' should be a non-strict inequality. These are typographical issues and do not affect the argument.
  3. [Remark 1] The sentence 'the value of i is recorded using ⌈log(d+1)⌉ additional bits only when it is between 1 and d−1' should read 'between 2 and d−2', because 1 and d−1 were already listed among the special values stored in the three-bit prefix.
  4. [Theorem 3, statement] The decoder in property (P1) is denoted by ϕ(a,b), whereas the labeling scheme in Definition 1 uses ξ for the decoder and ⟨λ,ϕ⟩ for the pair. The notation should be made consistent to avoid confusion.

Circularity Check

0 steps flagged · score 2.0 of 10

No circularity: the 4/3 log n bound is derived from the external product-structure theorem and a new strengthened bounded-treewidth scheme (Lemma 5); the only author-overlap citation ([GL07]) is not load-bearing.

full rationale

The derivation chain is not circular. Theorem 1 is explicitly conditional on efficient flatness (Definition 2), and for planar graphs that property is supplied by the external product-structure theorem of Dujmović et al. [DJM+19], whose authors do not overlap with this paper. The central new ingredient is Theorem 3, and in particular property (P2), which is obtained by replacing a crucial combinatorial element of [GL07] with a new bidecomposition lemma, Lemma 5, proved in full via Claims 1-4. The final bound is reached by optimizing the expression max{log n + log d, 2 log(n/d)} at d = n^{1/3}, giving 4/3 log n; this is a calculation, not a fitted parameter renamed as a prediction. The only self-citation is [GL07], co-authored by Gavoille, used as a previously published theorem for bounded-treewidth labeling schemes; the improvement over [GL07] depends on the new Lemma 5 and the block/superposition construction, so this citation is minor and not load-bearing. No step reduces to its own input by definition.

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

No empirical free parameters. The block width d=n^{1/3} and epsilon=1/log n are chosen by asymptotic optimization, not fitted to data. The paper introduces the mathematical abstraction 'efficiently flat class' and the notion of a bidecomposition, but these are definitions, not new physical entities. The derivation rests on two imported theorems and standard algorithmic lemmas.

assumptions (3)
  • domain assumption Product structure theorem / efficient flatness: every graph in C embeds into H⊠P with treewidth(H) <= w and P a path, computable in polynomial time.
    Imported from [DJM+19] (Definition 2 and Section 2). The entire construction of Theorem 1 takes this embedding as its starting point; Claims 6 and 7 depend on it.
  • domain assumption Bounded-treewidth labeling theorem (Theorem 2, [GL07]): graphs of treewidth at most k have labels of length log n + O(k log log n).
    Used for the border graph G1 and as the basis for the strengthened scheme in Theorem 3; it is a published theorem taken as input.
  • domain assumption Linear-time computation of an optimal-width tree decomposition for fixed treewidth (Bodlaender [Bod96]).
    Invoked in the algorithmic implementation of Lemma 5, specifically for separator construction and recursive bidecomposition.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Shorter Labeling Schemes for Planar Graphs." pith.science (2026). https://pith.science/paper/W3CUPJTN

@misc{pith2026190803341,
  author       = {Pith},
  title        = {Pith review of: Shorter Labeling Schemes for Planar Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/W3CUPJTN}},
  note         = {Machine review of arXiv:1908.03341}
}
abstract

An \emph{adjacency labeling scheme} for a given class of graphs is an algorithm that for every graph $G$ from the class, assigns bit strings (labels) to vertices of $G$ so that for any two vertices $u,v$, whether $u$ and $v$ are adjacent can be determined by a fixed procedure that examines only their labels. It is known that planar graphs with $n$ vertices admit a labeling scheme with labels of bit length $(2+o(1))\log{n}$. In this work we improve this bound by designing a labeling scheme with labels of bit length $(\frac{4}{3}+o(1))\log{n}$. In graph-theoretical terms, this implies an explicit construction of a graph on $n^{4/3+o(1)}$ vertices that contains all planar graphs on $n$ vertices as induced subgraphs, improving the previous best upper bound of $n^{2+o(1)}$. Our scheme generalizes to graphs of bounded Euler genus with the same label length up to a second-order term. All the labels of the input graph can be computed in polynomial time, while adjacency can be decided from the labels in constant time.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

51 extracted references · 29 canonical work pages

  1. [1]

    Near-Optimal Induced Universal Graphs for Bounded Degree Graphs

    M. Abrahansen, S. Alstrup, M. B k Tejs Knudsen, and M. St \"o ckel , Near-optimal induced universal graphs for cycles and paths , Tech. Rep. http://arxiv.org/abs/1607.04911v2 1607.04911v2 [cs.DS] , arXiv, July 2016

    work page Pith review arXiv 2016

  2. [2]

    Abraham, S

    I. Abraham, S. Chechik, C. Gavoille, and D. Peleg , Forbidden-set distance labels for graphs of bounded doubling dimension , ACM Transactions on Algorithms, 12 (2016), pp. 22:1--22:17. doi : http://doi.org/10.1145/2818694 10.1145/2818694

    doi:10.1145/2818694 2016

  3. [3]

    H. Acan, S. Chakraborty, S. Jo, and S. S. Rao , Succinct data structures for families of interval graphs , Tech. Rep. http://arxiv.org/abs/1902.09228 1902.09228v1 [cs.DS] , arXiv, February 2019

    work page Pith review arXiv 1902

  4. [4]

    Alstrup, S

    S. Alstrup, S. Dahlgaard, and M. B k Tejs Knudsen , Optimal induced universal graphs and adjacency labeling for trees , Journal of the ACM, 64 (2017), pp. 27:1--27:22. doi : http://doi.org/10.1145/3088513 10.1145/3088513

    doi:10.1145/3088513 2017

  5. [5]

    Alstrup, C

    S. Alstrup, C. Gavoille, E. B. Halvorsen, and H. Petersen , Simpler, faster and shorter labels for distances in graphs , in 27^ th Symposium on Discrete Algorithms, SODA 2016, ACM-SIAM, January 2016, pp. 338--350. doi : http://doi.org/10.1137/1.9781611974331.ch25 10.1137/1.9781611974331.ch25

    doi:10.1137/1.9781611974331.ch25 2016

  6. [6]

    Alstrup, C

    S. Alstrup, C. Gavoille, H. Kaplan, and T. Rauhe , Nearest common ancestors: A survey and a new algorithm for a distributed environment , Theory of Computing Systems, 37 (2004), pp. 441--456. doi : http://doi.org/10.1007/s00224-004-1155-5 10.1007/s00224-004-1155-5

    doi:10.1007/s00224-004-1155-5 2004

  7. [7]

    Alstrup, E

    S. Alstrup, E. B. Halvorsen, and K. Green Larsen , Near-optimal labeling schemes for nearest common ancestors , in 25^ th Symposium on Discrete Algorithms, SODA 2014, ACM-SIAM, January 2014, pp. 972--982. doi : http://doi.org/10.1137/1.9781611973402.72 10.1137/1.9781611973402.72

    doi:10.1137/1.9781611973402.72 2014

  8. [8]

    Alstrup, H

    S. Alstrup, H. Kaplan, M. Thorup, and U. Zwick , Adjacency labeling schemes and induced-universal graphs , in 47^ th Annual ACM Symposium on Theory of Computing, STOC 2015, ACM Press, June 2015, pp. 625--634. doi : http://doi.org/10.1145/2746539.2746545 10.1145/2746539.2746545

    arXiv 2015

Show all 51 references
  1. [9]

    Alstrup, H

    S. Alstrup, H. Kaplan, M. Thorup, and U. Zwick , Adjacency labeling schemes and induced-universal graphs , SIAM Journal on Discrete Mathematics, 33 (2019), pp. 116--137. doi : http://doi.org/10.1137/16M1105967 10.1137/16M1105967

    2019 doi

  2. [10]

    Alon , Asymptotically optimal induced universal graphs , Geometric and Functional Analysis, 27 (2017), pp

    N. Alon , Asymptotically optimal induced universal graphs , Geometric and Functional Analysis, 27 (2017), pp. 1--32. doi : http://doi.org/10.1007/s00039-017-0396-9 10.1007/s00039-017-0396-9

    2017 doi

  3. [11]

    Alstrup and T

    S. Alstrup and T. Rauhe , Small induced-universal graphs and compact implicit graph representations , in 43^ rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2002, IEEE Computer Society Press, November 2002, pp. 53--62. doi : http://doi.org/10.1109/SFCS.2002.1...

    2002 arXiv

  4. [12]

    Adjiashvili and N

    D. Adjiashvili and N. Rotbart , Labeling schemes for bounded degree graphs , in 41^ st International Colloquium on Automata, Languages and Programming, ICALP 2014, vol. 8573 of Lecture Notes in Computer Science (ARCoSS), Springer, July 2014, pp. 375--386. doi : http://doi.org/...

    2014 doi

  5. [13]

    Babai, F

    L. Babai, F. R. K. Chung, P. Erd o s, R. L. Graham, and J. H. Spencer , On graphs which contain all sparse graphs , Annals of Discrete Mathematics, 12 (1982), pp. 21--26. doi : http://doi.org/10.1016/S0304-0208(08)73486-8 10.1016/S0304-0208(08)73486-8

    1982 doi

  6. [14]

    Bonichon, C

    N. Bonichon, C. Gavoille, and A. Labourel , Short labels by traversal and jumping , in 13^ th International Colloquium on Structural Information & Communication Complexity, SIROCCO 2006, vol. 4056 of Lecture Notes in Computer Science, Springer, July 2006, pp. 143--156. doi : h...

    2006 doi

  7. [15]

    Bonamy, C

    M. Bonamy, C. Gavoille, and M. Pilipczuk , Shorter labeling schemes for planar graphs , in 31^ st Symposium on Discrete Algorithms, SODA 2020, SIAM , 2020, pp. 446--462. doi : http://doi.org/10.1137/1.9781611975994.27 10.1137/1.9781611975994.27 , https://doi.org/10.1137/1.9781...

    2020 doi

  8. [16]

    H. L. Bodlaender , A linear time algorithm for finding tree-decompositions of small treewidth , SIAM Journal on Computing, 25 (1996), pp. 1305--1317. doi : http://doi.org/10.1137/S0097539793251219 10.1137/S0097539793251219

    1996 doi

  9. [17]

    Butler , Induced-universal graphs for graphs with bounded maximum degree , Graphs and Combinatorics, 25 (2009), pp

    S. Butler , Induced-universal graphs for graphs with bounded maximum degree , Graphs and Combinatorics, 25 (2009), pp. 461--468. doi : http://doi.org/10.1007/s00373-009-0860-x 10.1007/s00373-009-0860-x

    2009 doi

  10. [18]

    M. R. Capalbo , Small universal graphs for bounded-degree planar graphs , Combinatorica, 22 (2002), pp. 345--359. doi : http://doi.org/10.1007/s004930200017 10.1007/s004930200017

    2002 doi

  11. [19]

    Chalopin, D

    J. Chalopin, D. Gon c alves, and P. Ochem , Planar graphs have 1-string representations , Discrete & Computational Geometry, 43 (2010), pp. 626--647. doi : http://doi.org/10.1007/s00454-009-9196-9 10.1007/s00454-009-9196-9

    2010 doi

  12. [20]

    F. R. K. Chung , Universal graphs and induced-universal graphs , Journal of Graph Theory, 14 (1990), pp. 443--454. doi : http://doi.org/10.1002/jgt.3190140408 10.1002/jgt.3190140408

    1990 doi

  13. [21]

    Dujmovi\' c , L

    V. Dujmovi\' c , L. Esperet, G. Joret, B. Walczak, and D. R. Wood , Planar graphs have bounded nonrepetitive chromatic number , Tech. Rep. http://arxiv.org/abs/1904.05269 1904.05269v1 [math.CO] , arXiv, 2019

    1904 arXiv

  14. [22]

    Dujmovi\'c , L

    V. Dujmovi\'c , L. Esperet, G. Joret, C. Gavoille, P. Micek, and P. Morin , Adjacency labelling for planar graphs (and beyond) , Tech. Rep. 2003.04280 [math.CO], arXiv, March 2020

    2003 arXiv

  15. [23]

    de Fraysseix, P

    H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl , On triangle contact graphs , Combinatorics, Probability & Computing, 3 (1994), pp. 233--246. doi : http://doi.org/10.1017/S0963548300001139 10.1017/S0963548300001139

    1994 doi

  16. [24]

    Dvo r \' a k, T

    Z. Dvo r \' a k, T. Huynh, G. Joret, C. Liu, and D. R. Wood , Notes on graph product structure theory , Tech. Rep. 2001.08860 [math.CO], arXiv, January 2020

    2001 arXiv

  17. [25]

    Dujmovi\' c , G

    V. Dujmovi\' c , G. Joret, P. Micek, P. Morin, T. Ueckerdt, and D. R. Wood , Planar graphs have bounded queue-number , in 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, IEEE Computer Society, 2019, pp. 862--875. doi : http://doi.org/10.1109/FOCS.2019...

    2019

  18. [26]

    Dujmovi\'c , P

    V. Dujmovi\'c , P. Morin, and D. R. Wood , The structure of k -planar graphs , Tech. Rep. 1907.05168 [math.CO], arXiv, July 2019

    1907 arXiv

  19. [27]

    Esperet, A

    L. Esperet, A. Labourel, and P. Ochem , On induced-universal graphs for the class of bounded-degree graphs , Information Processing Letters, 108 (2008), pp. 255--260. doi : http://doi.org/10.1016/j.ipl.2008.04.020 10.1016/j.ipl.2008.04.020

    2008 doi

  20. [28]

    Fraigniaud and C

    P. Fraigniaud and C. Gavoille , Routing in trees , in 28^ th International Colloquium on Automata, Languages and Programming, ICALP 2001, vol. 2076 of Lecture Notes in Computer Science, Springer, July 2001, pp. 757--772. doi : http://doi.org/10.1007/3-540-48224-5_62 10.1007/3-...

    2001 doi

  21. [29]

    Freedman, P

    O. Freedman, P. Gawrychowski, P. K. Nicholson, and O. Weimann , Optimal distance labeling schemes for trees , in 36^ th Annual ACM Symposium on Principles of Distributed Computing, PODC 2017, ACM Press, July 2017, pp. 185--194. doi : http://doi.org/10.1145/3087801.3087804 10.1...

    2017

  22. [30]

    Fraigniaud and A

    P. Fraigniaud and A. Korman , Compact ancestry labeling schemes for XML trees , in 21^ st Symposium on Discrete Algorithms, SODA 2010, ACM-SIAM, January 2010, pp. 458--466. doi : http://doi.org/10.1137/1.9781611973075.38 10.1137/1.9781611973075.38

    2010 doi

  23. [31]

    Fraigniaud and A

    P. Fraigniaud and A. Korman , An optimal ancestry scheme and small universal posets , in 42^ nd Annual ACM Symposium on Theory of Computing, STOC 2010, ACM Press, June 2010, pp. 611--620. doi : http://doi.org/10.1145/1806689.1806773 10.1145/1806689.1806773

    2010

  24. [32]

    Gon c alves, L

    D. Gon c alves, L. Isenmann, and C. Pennarun , Planar graphs as L -intersection or L -contact graphs , in 29^ th Symposium on Discrete Algorithms, SODA 2018, ACM-SIAM, 2018, pp. 172--184. doi : http://doi.org/10.1137/1.9781611975031.12 10.1137/1.9781611975031.12

    2018 doi

  25. [33]

    Gawrychowski, A

    P. Gawrychowski, A. Kosowski, and P. Uzna\'nski , Sublinear-space distance labeling using hubs , in 30^ th International Symposium on Distributed Computing, DISC 2016, vol. 9888 of Lecture Notes in Computer Science, Springer, September 2016, pp. 230--242. doi : http://doi.org/...

    2016 doi

  26. [34]

    Gavoille and A

    C. Gavoille and A. Labourel , Shorter implicit representation for planar graphs and bounded treewidth graphs , in 15^ th Annual European Symposium on Algorithms, ESA 2007, vol. 4698 of Lecture Notes in Computer Science, Springer, October 2007, pp. 582--593. doi : http://doi.or...

    2007 doi

  27. [35]

    Gavoille and D

    C. Gavoille and D. Peleg , Compact and localized distributed data structures , Distributed Computing, 16 (2003), pp. 111--120. doi : http://doi.org/10.1007/s00446-002-0073-5 10.1007/s00446-002-0073-5 . PODC 20-Year Special Issue

    2003 doi

  28. [36]

    Gavoille and C

    C. Gavoille and C. Paul , Optimal distance labeling for interval graphs and related graphs families , SIAM Journal on Discrete Mathematics, 22 (2008), pp. 1239--1258. doi : http://doi.org/10.1137/050635006 10.1137/050635006

    2008 doi

  29. [37]

    Gawrychowski and P

    P. Gawrychowski and P. Uzna\'nski , A note on distance labeling in planar graphs , Tech. Rep. http://arxiv.org/abs/1611.06529 1611.06529v1 [cs.DS] , arXiv, November 2016

    2016 arXiv

  30. [38]

    M. Katz, N. A. Katz, A. Korman, and D. Peleg , Labeling schemes for flow and connectivity , SIAM Journal on Computing, 34 (2004), pp. 23--40. doi : http://doi.org/10.1137/S0097539703433912 10.1137/S0097539703433912

    2004 doi

  31. [39]

    Kannan, M

    S. Kannan, M. Naor, and S. Rudich , Implicit representation of graphs , in 20^ th Annual ACM Symposium on Theory of Computing, STOC 1988, ACM Press, May 1988, pp. 334--343. doi : http://doi.org/10.1145/62212.62244 10.1145/62212.62244

    1988

  32. [40]

    u ber die Verhandlungen der S \

    P. Koebe , Kontaktprobleme der konformen abbildung , Berichte \"u ber die Verhandlungen der S \"a chsische Akademie der Wissenschaften zu Leipzig, Mathematisch-Physische Klasse, 88 (1936), pp. 141--164

    1936

  33. [41]

    Peleg , Informative labeling schemes for graphs , in 25^ th International Symposium on Mathematical Foundations of Computer Science, MFCS 2000, vol

    D. Peleg , Informative labeling schemes for graphs , in 25^ th International Symposium on Mathematical Foundations of Computer Science, MFCS 2000, vol. 1893 of Lecture Notes in Computer Science, Springer, August 2000, pp. 579--588. doi : http://doi.org/10.1007/3-540-44612-5_53...

    doi

  34. [42]

    Peleg , Informative labeling schemes for graphs , Theoretical Computer Science, 340 (2005), pp

    D. Peleg , Informative labeling schemes for graphs , Theoretical Computer Science, 340 (2005), pp. 577--593. doi : http://doi.org/10.1016/j.tcs.2005.03.015 10.1016/j.tcs.2005.03.015

    2005 doi

  35. [43]

    C. J. Rhee, Y. D. Liang, S. K. Dhall, and S. Lakshmivarahan , Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs , Information Processing Letters, 49 (1994), pp. 45--50. doi : http://doi.org/10.1016/0020-0190(94)90053-1 10.1016/00...

    1994 doi

  36. [44]

    Rotbart , New Ideas on Labeling Schemes , PhD thesis, University of Copenhagen, October 2016

    N. Rotbart , New Ideas on Labeling Schemes , PhD thesis, University of Copenhagen, October 2016. http://www.academia.edu/33855491/New_Ideas_on_Labeling_Schemes http://www.academia.edu/33855491/New_Ideas_on_Labeling_Schemes

    2016

  37. [45]

    Robertson and P

    N. Robertson and P. D. Seymour , Graph minors. XX . W agner's conjecture , Journal of Combinatorial Theory, Series B, 92 (2004), pp. 325--357. doi : http://doi.org/10.1016/j.jctb.2004.08.001 10.1016/j.jctb.2004.08.001

    2004 doi

  38. [46]

    Roditty and R

    L. Roditty and R. Tov , New routing techniques and their applications , in 34^ th Annual ACM Symposium on Principles of Distributed Computing, PODC 2015, ACM Press, July 2015, pp. 23--32. doi : http://doi.org/10.1145/2767386.2767409 10.1145/2767386.2767409

    2015

  39. [47]

    Schnyder , Planar graphs and poset dimension , Order, 5 (1989), pp

    W. Schnyder , Planar graphs and poset dimension , Order, 5 (1989), pp. 323--343. doi : http://doi.org/10.1007/BF00353652 10.1007/BF00353652

    1989 doi

  40. [48]

    J. P. Spinrad , Efficient Graph Representations , vol. 19 of Fields Institute Monographs, American Mathematical Society, 2003

    2003

  41. [49]

    Thomassen , Interval representations of planar graphs , Journal of Combinatorial Theory, Series B, 40 (1986), pp

    C. Thomassen , Interval representations of planar graphs , Journal of Combinatorial Theory, Series B, 40 (1986), pp. 9--20. doi : http://doi.org/10.1016/0095-8956(86)90061-4 10.1016/0095-8956(86)90061-4

    1986 doi

  42. [50]

    Thorup and U

    M. Thorup and U. Zwick , Compact routing schemes , in 13^ th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 2001, ACM Press, July 2001, pp. 1--10. doi : http://doi.org/10.1145/378580.378581 10.1145/378580.378581

    2001

  43. [51]

    write newline

    " write newline "" before.all 'output.state := FUNCTION output.doi doi empty 'skip " doi : http://doi.org/" doi * " " * doi * " " * output if FUNCTION output.url url empty 'skip " " url * " " * url * " " * output if FUNCTION output.isbn isbn empty 'skip " isbn : " isbn * outpu...

Pith tools

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