Pith. sign in

REVIEW 6 minor 22 references

Graph Stories in Small Area

T0 review · 0 major / 6 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 Every tree story admits a planar straight-line drawing in an (8W+1)×(8W+1) grid; some planar graph stories force Ω(n)×Ω(n) area.

desk verdict Solid constructive small-area bounds for path and tree stories; the tree proof is heavy but the wedge invariant holds up — worth refereeing. read the letter →

arxiv 1908.09318 v2 pith:JVGDZO36 submitted 2019-08-25 cs.DS cs.CGcs.DM

Manuel Borrazzo , Giordano Da Lozzo , Giuseppe Di Battista , Fabrizio Frati , Maurizio Patrignani This is my paper · ORCID
classification cs.DScs.CGcs.DM MSC 05C6268R1005C10
keywords graphstoriesdynamicgraphsplanarstraight-linedrawingsgridwindowsizetreessimultaneousembeddingsstreamingdrawing
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

Graph stories model a graph whose vertices arrive one at a time and stay for a fixed number $W$ of time steps; a drawing story must show each time window as a planar straight-line drawing, with every vertex pinned to a single position. This paper proves that paths and trees are tractable: any tree story on $n$ vertices admits a planar straight-line drawing story on an $(8W+1)\times(8W+1)$ grid, constructible in $O(n)$ time, and any path story fits on a $2W\times 2W$ grid. Hence the area needed at any moment depends only on how many vertices coexist, not on how many have ever appeared. Conversely, the paper exhibits planar graph stories (nested triangles with window size $9$) for which every drawing story requires $\Omega(n)\times\Omega(n)$ area, so the window-only area guarantee cannot extend to all planar graphs. The algorithms keep every vertex at the same coordinates across all frames and encode the entire story in $O(n)$ space.

What carries the argument

The paper's engine is a family of 'arrow drawings' of rooted ordered forests: planar, straight-line, strictly monotone in both the up and left directions, order-preserving grid drawings in which each vertex $v$ is the apex of a wedge $S(v)$ — obtained by rotating a rightward ray clockwise down to a half-line of slope $-2$ — and Condition (v) of Definition 1 requires this wedge to meet the drawing only along that half-line. The construction partitions the tree into buckets $B_1,\dots,B_h$ of $W$ vertices by arrival time, adds dummy edges to keep bucket labels of adjacent vertices within $1$, decomposes the resulting ordered tree into 'pertinent components' layered in sets $R_j$, and colours these components into four per-bucket forests, one for each cardinal direction. Each forest is drawn by a recursive X-Drawer in its own quadrant; because every time window is contained in the union of two consecutive buckets (Property 1), the whole story is planar if each induced drawing $T[B_i\cup B_{i+1}]$ is. Lemma 4 proves that by an exhaustive case analysis over where the two endpoints of each edge lie, with the wedge condition supplying the geometric fact (Property 4) that every vertex's wedge contains a common segment of the x-axis, so edges descending from one bucket to the next stay inside their endpoint's private cone and cannot cross.

What would settle it

Run the recursive X-Drawer on all rooted ordered forests with up to five vertices and $W\ge 4$, checking Condition (v) of Definition 1 after every recursive call; then assemble a tree story with $W=3$ or $4$ and verify that every frame $\Gamma[B_i\cup B_{i+1}]$ is planar. Any vertex whose wedge contains a point of the drawing off its own half-line, or any crossing in a frame, would provide a counterexample to Theorem 3's construction.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central claim comes in two parts. Upper bound: for every tree story $\langle T,\tau,W\rangle$ with $n$ vertices there exists a drawing story in which each frame is a planar straight-line grid drawing, each vertex never changes position, and every frame lies inside an $(8W+1)\times(8W+1)$ grid; the construction runs in $O(n)$ time, and the same machinery yields a $2W\times 2W$ bound for path stories. Lower bound: when the story is generated by an $n$-vertex nested-triangles planar graph with window size $9$, any planar straight-line drawing story with stationary vertices forces the induced drawing of the whole graph to be planar, and therefore any such story occupies $\Omega(n)\times\Omega(n)$ area. Together the two parts carve out the exact frontier of the 'small area' guarantee within the family of planar graphs.

Load-bearing premise

The whole tree construction rests on the claim that the recursive X-Drawer can always produce an 'arrow drawing' satisfying the wedge condition — for every vertex, the wedge $S(v)$ intersects the drawing only along its own half-line; that invariant is what every crossing argument in Lemma 4 leans on, and if a forest ever failed to admit such a drawing, the planarity proof for tree stories would break.

Editorial extensions

If this is right

  • For any stream of vertices with at most $W$ alive at once, the drawing of a tree story never needs more than $(8W+1)^2$ area per frame, regardless of how long the stream is.
  • The whole drawing story is produced in $O(n)$ time and stored in $O(n)$ space, so the construction scales to very long vertex streams as long as $W$ stays small.
  • Path stories inherit the guarantee with a smaller constant: every frame fits on a $2W\times 2W$ grid.
  • The nested-triangles lower bound shows that for general planar graphs no such window-only area bound is possible if vertices are stationary and frames must stay planar; additional structural restrictions are necessary.

Reading between the lines

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

  • The bucket-plus-directional-forest scheme is a plausible template for outerplanar and series-parallel graph stories; the paper lists these as open problems, and its own remark that cycles fit in $(4W+2)^2$ area points in that direction.
  • The wedge-visibility invariant is a reusable primitive: any dynamic drawing problem with fixed vertex positions and bounded-lifetime edges could try to satisfy an analogous 'each vertex sees its future neighbours inside a private cone' condition.
  • The lower bound uses a very specific story (nested triangles with $W=9$); probing intermediate classes such as outerplanar or treewidth-bounded graphs could identify precisely where the transition from window-only area to graph-size-dependent area happens.
  • The constants $2$ and $8$ are not claimed optimal; an implementation-level exhaustive search over small trees could test whether a different bucket layout or wedge slope shrinks the tree bound.
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

0 major / 6 minor

Summary. The paper introduces the graph story model, in which vertices appear at distinct times and remain active for a fixed window W, and the story is the sequence of induced subgraphs on the active vertices. A drawing story is a sequence of planar straight-line grid drawings in which each vertex keeps the same position whenever it appears. The paper proves three results. Theorem 1 shows that some planar graph stories, namely nested-triangles graphs with W=9, cannot be drawn in area depending only on W: every drawing story induces a planar straight-line drawing of the whole graph, hence requires Omega(n) by Omega(n) area. Theorem 2 shows that every path story can be drawn on a 2W by 2W grid in O(n) time by ordering vertices in overlapping x- and y-buckets. Theorem 3, the main contribution, shows that every tree story can be drawn on an (8W+1) by (8W+1) grid in O(n) time. The tree algorithm partitions the tree into buckets, adds dummy edges to make the bucket labels Lipschitz, groups vertices into four types of recursively constructed directed forest drawings, and uses a wedge-invariant argument to prove that the drawing induced by each pair of consecutive buckets is planar.

Significance. If the results hold, the paper makes a solid contribution to dynamic graph drawing. It gives the first small-area drawing-story results for trees in a model where only the window size is allowed to drive the area, and the nested-triangles lower bound shows that the restriction to trees (or other sparse families) is necessary rather than an artifact of the proof method. The algorithms are constructive and run in linear time, and the geometry is made explicit through the X-drawing Definition and the wedge invariant. The paper is self-contained, uses only standard tools such as Whitney's unique embedding theorem and known grid lower bounds, and does not fit parameters to its conclusions. The path result is simple and elegant, and the tree construction, with its four-direction forest packing and the case analysis in Lemma 4, is a substantial technical achievement even though the presentation would benefit from a few clarifications.

minor comments (6)
  1. [Section 4 (bucket definitions)] The definition of x-buckets applies the formula Bx_i = B_{2i-2} ∪ B_{2i-1} for i up to ceil((h+1)/2), but when h=2 this references the nonexistent bucket B_3. Please state explicitly that B_i is empty for i>h, or restrict the union to existing buckets. Similarly, the statement that every vertex belongs to exactly one y-bucket fails for h=1, since no y-bucket is defined; the proof should treat the h=1 case separately.
  2. [Section 5, Lemma 2] In the proof of Lemma 2 the symbol v is used both for the vertex chosen in B_{p-1} and for the representative of T* in B_p, which makes the construction hard to follow. Please disambiguate and state that the added edge connects the representative of the visited component for bucket B_{p-1} to the representative of T* for bucket B_p, so that the bucket difference of the new edge is exactly 1.
  3. [Section 5, Lemma 1, first inductive case] The proof that Condition (v) of Definition 1 holds for vertices of F1 cites only the induction hypothesis for the drawing Γ1. That hypothesis concerns intersections with the forest drawing Γ1, not with the newly added edges incident to r(T1). Please add the simple geometric observation that these new edges are contained in the half-plane x <= 1, whereas every wedge S(v) for v in F1 is contained in x >= 1, so the only possible intersection of a new edge with S(v) is at a child endpoint; if that child endpoint lies in S(v), then Condition (v) for Γ1 forces it to lie on l(v), which is allowed.
  4. [Section 5, Lemma 4] The final sentence of Lemma 4 asserts, without proof, that no edge overlaps a vertex in Γ[B_{i,i+1}]. This is a required part of planarity and should be justified explicitly. A concise argument would observe that an inter-bucket edge enters the neighboring quadrant only at the axis, where only roots are placed, and that within its own quadrant a vertex lying on such an edge would lie in the wedge of the edge's endpoint and contradict Condition (v).
  5. [Section 3, Theorem 1] The induction in Theorem 1 starts at m=9, so the cases n=3 and n=6 are not covered by the written proof. These cases are trivial because the induced drawing of the whole graph is just one of the planar story drawings, but they should be mentioned for completeness.
  6. [Section 5, Theorem 3] The proof uses implicitly that the four forest drawings associated with a pair of consecutive buckets occupy four disjoint quadrants of the plane. This is stated by citing Condition (i), but a sentence making the quadrant separation explicit would help the reader verify that different forest drawings cannot overlap and that vertices of distinct forests in the same story frame never coincide.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity identified; the constructions are proved from explicit invariants rather than assumed.

full rationale

The paper's central results are constructive and self-contained. Theorem 2 fixes vertex coordinates by x-bucket and y-bucket path orders and proves planarity because every G_t lies inside one such bucket, so no target property is fed back into the construction. For Theorem 3, Definition 1 introduces the X-drawing invariant (wedge nonintersection), but the correctness of the X-Drawer is not assumed: Lemma 1 proves the invariant inductively with explicit geometric checks for the root-wedge parts, and Lemma 4's crossing analysis uses those proved invariants plus coordinate-separation properties (above/below axes, left/right of axes). The lower bound in Theorem 1 is imported from standard external results on nested triangles graphs [8,12,13], not from any assumption of the drawing-story model; the citation to [13] is an overlapping-author reference, but it is one of several standard sources and is not used to define or justify the new algorithms. No fitted parameter is renamed as a prediction, no uniqueness theorem is imported from the authors' prior work, and no known result is merely relabeled. Hence there is no circular step and the paper's derivation chain is independent of its conclusions.

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

No free parameters or fitted constants appear. The paper introduces a new drawing standard (X-drawings) as a technique, not an empirical entity. The central claims rely on standard background theorems and the offline graph-story model.

assumptions (4)
  • standard math 3-connected planar graphs have a unique combinatorial embedding up to flip (Whitney's theorem).
    Invoked in Theorem 1 to assert that the cycle C_{m-3} bounds a face in any planar drawing of the nested triangles subgraph I_{m-3}.
  • standard math Known lower bounds on the grid area of straight-line planar drawings of the nested triangles graph (de Fraysseix-Pach-Pollack 1990, Dolev-Leighton-Trickey 1984, Frati-Patrignani 2007).
    Used at the end of Theorem 1 to conclude the Omega(n) by Omega(n) area lower bound once the induced drawing of G is shown planar.
  • domain assumption The input graph story is known offline: the entire vertex ordering and graph are available before drawing.
    The model assumes an offline setting, stated in Section 1; all algorithms are offline.
  • domain assumption Each vertex has a distinct appearance time and remains for exactly W time steps.
    This defines the graph story model used throughout; the bounds are stated for this model.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Graph Stories in Small Area." pith.science (2026). https://pith.science/paper/JVGDZO36

@misc{pith2026190809318,
  author       = {Pith},
  title        = {Pith review of: Graph Stories in Small Area},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JVGDZO36}},
  note         = {Machine review of arXiv:1908.09318}
}
abstract

We study the problem of drawing a dynamic graph, where each vertex appears in the graph at a certain time and remains in the graph for a fixed amount of time, called the window size. This defines a graph story, i.e., a sequence of subgraphs, each induced by the vertices that are in the graph at the same time. The drawing of a graph story is a sequence of drawings of such subgraphs. To support readability, we require that each drawing is straight-line and planar and that each vertex maintains its placement in all the drawings. Ideally, the area of the drawing of each subgraph should be a function of the window size, rather than a function of the size of the entire graph, which could be too large. We show that the graph stories of paths and trees can be drawn on a $2W \times 2W$ and on an $(8W + 1) \times (8W + 1)$ grid, respectively, where $W$ is the window size. These results are constructive and yield linear-time algorithms. Further, we show that there exist graph stories of planar graphs whose subgraphs cannot be drawn within an area that is only a function of $W$.

Figures

Figures reproduced from arXiv: 1908.09318 by the authors.

Figure 1
Figure 1. Examples of buckets, x-buckets, and y-buckets when W = 4. vertices, except for B1 and, possibly, the last x-bucket; see [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Construction of a -drawing: the first inductive case, in which k = 1 and m > 1. Lemma 1. The algorithm -Drawer constructs a -drawing of F in O(m) time. Proof. The algorithm -Drawer clearly runs in O(m) time. We now prove that the drawing Γ of F it constructs is a -drawing. This is trivial in the base case. In the first inductive case, we have k = 1 and m > 1. Recall that Γ has been obtained by placing r(T1) at (0, 4… view at source ↗
Figure 3
Figure 3. Construction of a -drawing: the second inductive case, in which k > 1. vertical line x := 1, by Condition ii of Definition 1 for Γ1, it follows that Γ is order-preserving. Third, that Γ is a grid drawing easily follows from the fact that Γ 0 1 is a translation by an integer vector of Γ1, which is a grid drawing by induction, and from the fact that r(T1) is placed at (0, 4W), by construction. We now prove that Γ sati… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Illustration for the proof of Theorem 3, with W = 12. The upper part of the figure shows the rooted ordered tree T; vertices and edges that are not in T[B1,2] are gray. A pertinent component P j i of T belongs to the bucket Bi; further, the index j represents the order…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 14 canonical work pages

  1. [1]

    Algorithmica 81(6), 2196–2221 (2019)

    Angelini, P., Bekos, M.A.: Hierarchical partial planarity. Algorithmica 81(6), 2196–2221 (2019). https://doi.org/10.1007/s00453-018-0530-6, https://doi.org/ 10.1007/s00453-018-0530-6

    work page doi:10.1007/s00453-018-0530-6 2019

  2. [2]

    In: Borgo, R., Maciejewski, R., Viola, I

    Beck, F., Burch, M., Diehl, S., Weiskopf, D.: The state of the art in vi- sualizing dynamic graphs. In: Borgo, R., Maciejewski, R., Viola, I. (eds.) Eurographics Conference on Visualization, EuroVis 2014 - State of the Art Reports, STARs, Swansea, UK, June 9-13, 2014. Eurographics Association (2014). https://doi.org/10.2312/eurovisstar.20141174, https://d...

    doi:10.2312/eurovisstar.20141174 2014

  3. [3]

    Binucci, C., Brandes, U., Di Battista, G., Didimo, W., Gaertler, M., Palladino, P., Patrignani, M., Symvonis, A., Zweig, K.A.: Drawing trees in a streaming model. Inf. Process. Lett. 112(11), 418–422 (2012). https://doi.org/10.1016/j.ipl.2012.02.011, https://doi.org/10.1016/j.ipl.2012.02.011

    work page doi:10.1016/j.ipl.2012.02.011 2012

  4. [4]

    In: Tamassia, R

    Bl¨ asius, T., Kobourov, S.G., Rutter, I.: Simultaneous embedding of planar graphs. In: Tamassia, R. (ed.) Handbook on Graph Drawing and Visualization., pp. 349–381. Chapman and Hall/CRC (2013)

    work page 2013

  5. [5]

    Com- put

    Braß, P., Cenek, E., Duncan, C.A., Efrat, A., Erten, C., Ismailescu, D., Kobourov, S.G., Lubiw, A., Mitchell, J.S.B.: On simultaneous planar graph embeddings. Com- put. Geom. 36(2), 117–130 (2007). https://doi.org/10.1016/j.comgeo.2006.05.006, https://doi.org/10.1016/j.comgeo.2006.05.006

    work page doi:10.1016/j.comgeo.2006.05.006 2007

  6. [6]

    Cohen, R.F., Di Battista, G., Tamassia, R., Tollis, I.G.: Dynamic graph drawings: Trees, series-parallel digraphs, and planar st-digraphs. SIAM J. Comput. 24(5), 970–1001 (1995). https://doi.org/10.1137/S0097539792235724, https://doi.org/ 10.1137/S0097539792235724

    work page doi:10.1137/s0097539792235724 1995

  7. [7]

    In: CIAC

    Da Lozzo, G., Rutter, I.: Planarity of streamed graphs. In: CIAC. LNCS, vol. 9079, pp. 153–166. Springer (2015)

    work page 2015

  8. [8]

    Combinatorica 10(1), 41–51 (1990)

    de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990)

    work page 1990

Show all 22 references
  1. [9]

    In: Kratochv´ ıl, J

    Demetrescu, C., Di Battista, G., Finocchi, I., Liotta, G., Patrignani, M., Pizzonia, M.: Infinite trees and the future. In: Kratochv´ ıl, J. (ed.) Graph Drawing, 7th Inter- national Symposium, GD’99, Stir´ ın Castle, Czech Republic, September 1999, Pro- ceedings. LNCS, vol. 173...

    1999 doi

  2. [10]

    Di Battista, G., Tamassia, R.: On-line planarity testing. SIAM J. Comput. 25(5), 956–997 (1996). https://doi.org/10.1137/S0097539794280736, https://doi.org/ 10.1137/S0097539794280736 20 M. Borrazzo et al

    1996 doi

  3. [11]

    Di Battista, G., Tamassia, R., Vismara, L.: Incremental convex planarity testing. Inf. Comput. 169(1), 94–126 (2001). https://doi.org/10.1006/inco.2001.3031, https: //doi.org/10.1006/inco.2001.3031

    2001

  4. [12]

    Advances in Computing Research 2 (1984)

    Dolev, D., Leighton, F., Trickey, H.: Planar embedding of planar graphs. Advances in Computing Research 2 (1984)

    1984

  5. [13]

    In: Hong, S., Nishizeki, T., Quan, W

    Frati, F., Patrignani, M.: A note on minimum-area straight-line drawings of planar graphs. In: Hong, S., Nishizeki, T., Quan, W. (eds.) 15th International Symposium on Graph Drawing (GD 2007). LNCS, vol. 4875, pp. 339–344. Springer (2007)

    2007

  6. [14]

    In: Wismath, S.K., Wolff, A

    Goodrich, M.T., Pszona, P.: Streamed graph drawing and the file maintenance problem. In: Wismath, S.K., Wolff, A. (eds.) Graph Drawing - 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers. LNCS, vol. 8242, pp. 256–267. Springe...

    2013 doi

  7. [15]

    In: Encyclopedia of Algorithms, pp

    Italiano, G.F.: Fully dynamic planarity testing. In: Encyclopedia of Algorithms, pp. 806–808 (2016). https://doi.org/10.1007/978-1-4939-2864-4 157, https://doi. org/10.1007/978-1-4939-2864-4_157

    2016 doi

  8. [16]

    Internet Mathematics 12(4), 239–280 (2016)

    Michail, O.: An introduction to temporal graphs: An algorithmic perspective. Internet Mathematics 12(4), 239–280 (2016)

    2016

  9. [17]

    In: Leighton, F.T., Goodrich, M.T

    Poutr´ e, J.A.L.: Alpha-algorithms for incremental planarity testing (preliminary version). In: Leighton, F.T., Goodrich, M.T. (eds.) Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montr´ eal, Qu´ ebec, Canada. pp. 706–715. ACM (19...

    1994

  10. [18]

    IEEE Trans

    Reingold, E.M., Tilford, J.S.: Tidier drawings of trees. IEEE Trans. Software Eng. 7(2), 223–228 (1981). https://doi.org/10.1109/TSE.1981.234519, https:// doi.org/10.1109/TSE.1981.234519

    1981

  11. [19]

    In: Tollis, I.G., Patrignani, M

    Rextin, A., Healy, P.: A fully dynamic algorithm to test the upward planarity of single-source embedded digraphs. In: Tollis, I.G., Patrignani, M. (eds.) Graph Drawing, 16th International Symposium, GD 2008, Heraklion, Crete, Greece, September 21-24, 2008. Revised Papers. LNCS...

    2008 doi

  12. [20]

    In: Graph Drawing

    Schaefer, M.: Picking planar edges; or, drawing a graph with a planar subgraph. In: Graph Drawing. LNCS, vol. 8871, pp. 13–24. Springer (2014)

    2014

  13. [21]

    In: Hu, Y., N¨ ollenburg, M

    Skambath, M., Tantau, T.: Offline drawing of dynamic trees: Algorithmics and document integration. In: Hu, Y., N¨ ollenburg, M. (eds.) Graph Drawing and Network Visualization - 24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers....

    2016 doi

  14. [22]

    American Journal of Mathematics 54(1), 150–168 (1932), http://www.jstor.org/stable/2371086

    Whitney, H.: Congruent graphs and the connectivity of graphs. American Journal of Mathematics 54(1), 150–168 (1932), http://www.jstor.org/stable/2371086

    1932

Pith tools

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