{"id":"c84cc86d-befa-4d62-9030-4393a165bc09","arxiv_id":"1908.09318","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Path stories admit planar straight-line drawing stories on a 2W by 2W grid, tree stories on an (8W+1) by (8W+1) grid, and certain planar graph stories require Omega(n) by Omega(n) area.","lead":"This paper introduces graph stories, dynamic graphs where each vertex appears for a fixed time window, and shows that paths and trees can be drawn on small grids whose size depends only on the window size. It also proves that some planar graph stories cannot be drawn in such small areas, so the positive results cannot extend to all planar graphs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The reader's weakest assumption correctly identifies the X-drawing wedge invariant as the load-bearing condition. I reviewed the recursive X-Drawer construction, the geometric identities used to preserve Condition (v), the separation arguments in the k>1 case, and the role of Property 4 in Lemma 4. I also checked the subtle ordering argument in Claim 1, including the Phase 4 R-group ordering that rules out u being the LCA of v and z. The proof of Lemma 2 for dummy edges is linear-time and maintains the needed |b(u)-b(v)|<=1 invariant. The lower bound for nested triangles graphs is standard and the induction showing the induced drawing of G is planar is consistent. The main limitation is that the tree proof is intricate and would benefit from a machine-checked formalization or a randomized/exhaustive implementation test, but this is a verification suggestion rather than a detected flaw. No adjustment to the ACCEPT verdict is warranted.","tokens_in":18615,"tokens_out":40754,"duration_ms":397519,"concrete_test":"Implement X-Drawer and the full Theorem 3 construction; for all rooted ordered forests with total size m <= W <= 6 and all tree stories with n <= 10 and W <= 4, verify that every produced X-drawing satisfies Definition 1(i)-(v) and that every drawing Gamma_t is planar, with no edge crossings and no vertex-edge overlaps. Any violation would localize a failure to Lemma 1 or Lemma 4.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I examined the most delicate dependency of the central claim: Definition 1(v)'s wedge invariant and its use in Lemma 4. The recursive proof of Lemma 1 checks the root case by identifying the part of S(r(T1)) below y=4W-2 with S(r(T(u_l))); this is geometrically sound because the two wedges and their boundary half-lines coincide on that half-plane, and the k>1 case separates T1 from F2 by a horizontal line. Property 4's containment of the x-axis segment in every S(v) follows from the triangle bound in Property 3, since all vertices satisfy x_v + y_v/2 <= 2W. In the delicate Case (iv) of Lemma 4, Claim 1 reduces a potential crossing to u lying inside S(w); the proof that u is not the LCA of v and z uses Phase 4's R_j-first ordering, which forces the child on the z-path to precede the R_{j+1} root v, so the contradiction holds. Vertex-edge overlaps are asserted to follow by analogous arguments; any such overlap would produce an edge-edge crossing unless the vertex is isolated, and the same wedge-separation arguments rule out isolated vertices on inter-bucket edges. I found no concrete gap in the argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":18814,"tokens_out":51568,"duration_ms":495116,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Section 4 (bucket definitions)"},{"comment":"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.","section":"Section 5, Lemma 2"},{"comment":"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.","section":"Section 5, Lemma 1, first inductive case"},{"comment":"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).","section":"Section 5, Lemma 4"},{"comment":"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.","section":"Section 3, Theorem 1"},{"comment":"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.","section":"Section 5, Theorem 3"}],"recommendation":"minor_revision","confidential_remarks":"The paper is a strong fit for a graph drawing journal and I see no novelty or scope concerns. The technical core is sound and unusually detailed; the requested changes are local clarifications rather than corrections to the main arguments."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a solid graph-drawing paper that delivers what it promises. It introduces the graph story model with fixed vertex positions and window size W, gives a clean 2W x 2W grid for path stories and an (8W+1)x(8W+1) grid for tree stories, and shows with a standard nested-triangles lower bound that arbitrary planar graph stories cannot be drawn in area depending only on W. The path result is a neat adaptation of simultaneous geometric embeddings; the tree result is the real work, built on X-drawings with wedge invariants that control visibility between bucket layers. I went through the delicate part (Definition 1(v), Lemma 1, Lemma 4) and the stress-test note is right: I find no gap. The wedge invariant holds up, and the case analysis in Lemma 4 is internally consistent.\n\nSoft spots, in proportion. The tree proof is dense—Lemma 4 alone has four cases and a claim with subcases. It is not machine-checked, and I would not want to certify it by eye without more figures, but that is a presentation issue, not a correctness flaw. The lower bound is textbook (nested triangles plus known grid lower bounds), so no new technique there. The model itself is restrictive: vertices appear once, in a fixed order, and cannot move. That is acknowledged in the open problems, so it is not a hidden flaw. The citation pattern is fair; the paper properly distinguishes itself from streaming tree drawing and geometric simultaneous embeddings. The running-time claim of O(n) for the tree story depends on the bucket/pertinent-component construction, which is plausible; I did not find a hidden super-linear step.\n\nBottom line: this deserves a serious referee. The main results are new, the proofs are serious, and the paper is self-contained against external benchmarks. It will be useful to dynamic graph drawing people and to anyone working on simultaneous embeddings. I would support acceptance at a good graph drawing venue; revision effort should go into readability of the tree section—maybe a full-page figure for Lemma 4 or a sketch of the X-drawer recursion—rather than the mathematics.","headline":"Solid constructive small-area bounds for path and tree stories; the tree proof is heavy but the wedge invariant holds up — worth refereeing.","tokens_in":19300,"tokens_out":2780,"would_cite":true,"duration_ms":29147,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C62","68R10","05C10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every tree story admits a planar straight-line drawing in an (8W+1)×(8W+1) grid; some planar graph stories force Ω(n)×Ω(n) area.","keywords":["graph stories","dynamic graphs","planar straight-line drawings","grid drawings","window size","trees","simultaneous embeddings","streaming graph drawing"],"falsifier":"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.","tokens_in":18456,"feed_emoji":"🌲","tokens_out":12142,"duration_ms":112690,"temperature":0.7,"pith_summary":"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.","feed_headline":"Dynamic trees draw into an (8W+1) by (8W+1) grid","feed_subtitle":"Each W-vertex window stays planar and straight-line; nothing moves as the tree grows.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Provides the earlier $O(W^3)$-area streaming tree-drawing result that the tree-story bound improves upon in the fixed-lifetime vertex model.","marker":"[3]"},{"why":"Source of the simultaneous-geometric-embedding technique that the path-story construction is explicitly modelled on.","marker":"[5]"},{"why":"One of three references cited for the known $\\Omega(n)\\times\\Omega(n)$ lower bound on planar straight-line drawings used to finish Theorem 1.","marker":"[8]"},{"why":"Another of the references cited for the $\\Omega(n)\\times\\Omega(n)$ planar straight-line area lower bound invoked by the nested-triangles argument.","marker":"[12]"},{"why":"Third reference cited for the minimum-area planar straight-line drawing lower bound used in Theorem 1.","marker":"[13]"},{"why":"Establishes that 3-connected planar graphs have a unique combinatorial embedding, used to show each nested triangle bounds a face in the induction.","marker":"[22]"}],"fun_headline_variants":["Tree graph stories fit in (8W+1)² grid, paths in 4W²","Small-window graph stories: trees are easy, planar graphs aren't","W-window trees stay planar in (8W+1) by (8W+1)","Planar stories: some need Ω(n²) area even with small windows"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Tree graph stories fit in (8W+1)² grid, paths in 4W²","Small-window graph stories: trees are easy, planar graphs aren't","W-window trees stay planar in (8W+1) by (8W+1)","Planar stories: some need Ω(n²) area even with small windows"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00086,"raw_usage":{"total_tokens":3731,"prompt_tokens":943,"completion_tokens":2788,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":559,"completion_tokens_details":{"reasoning_tokens":2697}},"tokens_in":559,"tokens_out":2788,"duration_ms":18733,"temperature":1.0,"reasoning_tokens":2697,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:16:05.949679+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the earlier $O(W^3)$-area streaming tree-drawing result that the tree-story bound improves upon in the fixed-lifetime vertex model."},{"cited_title":"Com- put","cited_arxiv_id":null,"evidence_quote":"Source of the simultaneous-geometric-embedding technique that the path-story construction is explicitly modelled on."},{"cited_title":"Combinatorica 10(1), 41–51 (1990)","cited_arxiv_id":null,"evidence_quote":"One of three references cited for the known $\\Omega(n)\\times\\Omega(n)$ lower bound on planar straight-line drawings used to finish Theorem 1."},{"cited_title":"Advances in Computing Research 2 (1984)","cited_arxiv_id":null,"evidence_quote":"Another of the references cited for the $\\Omega(n)\\times\\Omega(n)$ planar straight-line area lower bound invoked by the nested-triangles argument."},{"cited_title":"In: Hong, S., Nishizeki, T., Quan, W","cited_arxiv_id":null,"evidence_quote":"Third reference cited for the minimum-area planar straight-line drawing lower bound used in Theorem 1."}],"review_version":1}