Pith. sign in

REVIEW 2 major objections 4 minor 29 references

Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Pith's one-line read Every outerplanar graph has a monotonic EPG representation with at most two bends.

desk verdict New bound for outerplanar monotonic EPG representations, with fixable gaps: the main construction is plausible but under-formalized, and one corollary contradicts an earlier theorem. read the letter →

arxiv 1908.01981 v4 pith:FPBK557X submitted 2019-08-06 math.CO cs.DM

classification math.COcs.DM MSC 05C6205C1005C75
keywords EPGrepresentationmonotonicpathsonagridbendnumberouterplanargraphsmaximalcactiforbiddeninducedsubgraphsintersection
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 proves that every outerplanar graph—a graph whose vertices can all be placed on the outer face of a drawing—can be represented as edge intersections of monotonic paths on a grid, with each path turning at most twice. It then pins down the exact minimum bend count for two important subclasses: maximal outerplanar graphs have monotonic bend number 0 or 2, while cacti have bend number 0 or 1. All proofs are constructive and the representations are built in polynomial time.

What carries the argument

The central device is the free part $R_v$ of an already-drawn path $P_v$, an unused stretch of its lower horizontal segment where Algorithm 2.2 places every newly constructed path. A 'nice labeling' orders the vertices counterclockwise around an added universal vertex, and this ordering has a separation property that keeps the free parts disjoint until they are used, ensuring that new paths intersect exactly the paths they are meant to intersect. The characterizations rest on two auxiliary graphs: the almost-dual graph (the tree formed by the triangular faces of a maximal outerplanar graph) and the reduced graph (the graph obtained by keeping only the vertices and edges that belong to copies of $S_3$).

What would settle it

Implement Algorithm 2.2 and check, for every exploration step, that the free part $R_{v_i}$ is clear of previously constructed paths; the first violation is a concrete counterexample to Lemma 2.6 and hence to Theorem 2.7. More directly, any outerplanar graph whose monotonic bend number exceeds 2 would refute the theorem.

Watch

Extended reading notes

Core claim

The paper's central theorem, Theorem 2.7, states that every outerplanar graph lies in $B_2^m$: there is a grid drawing in which each vertex is a monotonic path (ascending in both rows and columns) with at most two bends, and two paths share a grid edge exactly when the corresponding vertices are adjacent. The proof is algorithmic: Algorithm 2.2 constructs such a representation in linear time from a 'nice labeling' of the vertices. For maximal outerplanar graphs, the paper characterizes the (monotonic) bend number by forbidden induced subgraphs—$S_3$ for monotonic bend number 0, and $M_1$ or $M_1^\ell$ in the reduced graph for ordinary bend number 1. For cacti, it shows the bend number never exceeds 1 and is 0 exactly when the cactus avoids $M_2$, $M_3$, and cycles of length at least 4.

Load-bearing premise

The main algorithm's correctness rests on a geometric invariant: the free part of each already-drawn path stays untouched until the moment it is used, so new paths touch only the paths they are meant to touch.

Editorial extensions

If this is right

  • Every outerplanar graph has monotonic bend number at most 2, and the bound is best possible.
  • A maximal outerplanar graph has monotonic bend number 0 exactly when it contains no induced $S_3$; otherwise its monotonic bend number is 2.
  • A maximal outerplanar graph has ordinary bend number 1 exactly when its reduced graph is M-free.
  • Every cactus has monotonic bend number at most 1, and it is 0 exactly when it is $MC$-free.
  • All these representations can be constructed in polynomial time: linear for outerplanar graphs, quadratic for maximal outerplanar graphs with bend number 1.

Reading between the lines

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

  • If the free-part invariant of Algorithm 2.2 were formalized as an explicit algebraic condition, it might extend the same two-bend monotonic construction to all graphs of treewidth at most 2, where the monotonic bend number remains open.
  • The contrast between maximal outerplanar graphs (monotonic bend number jumps from 0 to 2) and cacti (never above 1) suggests that a single triangle surrounded by other triangles, not just the presence of cycles, is what forces two monotonic bends.
  • A computational check on all small outerplanar graphs could empirically test the invariant; the first unintended overlap would pinpoint a gap in the proof of Lemma 2.6.
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

2 major / 4 minor

Summary. The paper studies the (monotonic) bend number of outerplanar graphs, i.e., the minimum number of bends needed to represent a graph as an edge intersection graph of monotone paths on a grid. Its main theorem (Theorem 2.7) claims that every outerplanar graph is in Bm2, and it gives an algorithmic construction (Algorithm 2.2). For maximal outerplanar graphs, the paper characterizes membership in B0 (equivalently Bm1) by absence of S3, and membership in B1 by the absence of the induced configurations M1 and Mℓ1 in the reduced graph (Theorem 4.26); it also provides polynomial-time algorithms for these cases. For cacti, Theorem 5.9 claims that every cactus is in Bm1, and Theorem 5.7 characterizes those in B0 as the MC-free cacti. The paper concludes with a summary and open problems. The proofs are constructive and a number of subroutines are supplied as explicit algorithms.

Significance. If the results are correct, the paper makes a substantial contribution: it strengthens the known upper bound of 2 on the bend number of outerplanar graphs to the monotone setting, and it gives forbidden-induced-subgraph characterizations together with polynomial-time construction algorithms for two natural subclasses. The constructive nature of the proofs and the explicit algorithms are valuable, and the paper places its results well within the existing literature on EPG representations. However, the correctness of the central construction in Section 2 currently rests on an informal free-part invariant, and the cactus characterization in Section 5 contains a direct contradiction with Theorem 5.9. These issues affect load-bearing statements and must be resolved before the paper can be accepted.

major comments (2)
  1. [Section 2, Lemma 2.6 and Theorem 2.7(ii)] The correctness proof of Algorithm 2.2 depends on the assertion that each newly constructed path is contained in the free part Rvi of Pvi, where no other path has been constructed so far. This assertion is false as stated: the new two-bend monotone paths shown in Figure 1 have only their lower horizontal segment inside Rvi; their vertical segment and upper horizontal segment extend into the region above and to the right of Rvi. The proof of Lemma 2.6 asserts that the free-part invariant is maintained, but the only justification is the sentence 'new paths are constructed in such a way that this property is maintained' together with a reference to Figure 1. No coordinate-based or inductive argument shows that the parts of the new paths lying outside Rvi avoid previously constructed red paths or the upper segments of earlier green paths. Since this is exactly the property that rules out unintended intersections, Theorem 2.7(ii) is not fully proved. The gap is fixable, but the invariant and the placement of full paths must be formalized.
  2. [Section 5, Corollary 5.11] Corollary 5.11 states that for a cactus G, b(G) = bm(G) = 2 when G is not MC-free. This directly contradicts Theorem 5.9, which proves that every cactus belongs to Bm1 and hence has bm(G) ≤ 1. The concluding paragraph of Section 6 also states the correct value, namely 'Otherwise b(G)=bm(G)=1 holds'. Thus the value 2 in Corollary 5.11 is a substantive error in a stated theorem and must be corrected to 1. In addition, the abstract's phrase 'the cacti with (monotonic) bend number equal to 0, 1 and 2' is misleading, because by Theorem 5.9 no cactus has bend number 2; the cactus characterization should refer to bend numbers 0 and 1 only.
minor comments (4)
  1. [Abstract and Section 6] The abstract and the concluding summary claim characterizations for cacti with bend number 0, 1 and 2, but the paper proves that cacti have bend number at most 1; please adjust the wording to '0 and 1' for the cactus case.
  2. [Section 6, summary paragraph] There is a typo in the sentence 'For cacti the monotonic bend number and the bend number coincide and are bounded by 1, i.e. and b(G)=bm1(G)≤1 holds for every cactus G.' The expression 'bm1' should be 'bm(G)'.
  3. [Algorithm 2.1, line 8] The description 'the straight line segment of the edge {v0, vi} rotates counterclockwise around v0' is slightly imprecise; it is the ray from v0 through the vertex vi that rotates around v0. Please rephrase for clarity.
  4. [Lemma 2.6, proof] The proof relies heavily on Figure 1 for the placement of full paths and free parts; since this figure is the only justification for a key invariant, the authors should either add explicit coordinate descriptions or a formal inductive invariant so that the construction is machine-checkable.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the outerplanar Bm2 construction and the forbidden-subgraph characterizations are self-contained or import external results, and no prediction reduces to a fitted input or self-citation.

full rationale

The paper's central result, Theorem 2.7, is proved by an explicit construction, Algorithm 2.2, whose correctness depends on the path separation property and the free-part invariant in Lemma 2.6. That invariant is stated informally and justified partly by reference to Figure 1 rather than by a fully formalized coordinate argument, but this is a proof-gap or robustness concern, not circularity: the invariant is not assumed as an input, and the algorithm's output is not used to define the property it is supposed to establish. The lower-bound imports are genuinely external and non-self-referential: S3 not in Bm1 is taken from Cameron, Chaplick and Hoang [14], Sn not in B1 from Golumbic, Lipshteyn and Stern [24], the edge-clique/claw-clique structural lemma from [23], and the existence of an outerplanar graph not in B1 from Biedl and Stern [6]. The characterization results for maximal outerplanar graphs and cacti are likewise derived through constructive algorithms with proofs in both directions, using the external lower-bound results only as necessary conditions and providing independent constructions for sufficiency. There are no fitted parameters, no quantity is renamed as a prediction, and no load-bearing step is justified solely by a self-citation from the present authors. Consequently the derivation chain does not reduce to its own inputs, and the appropriate circularity score is 0.

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

The paper introduces no new free parameters or invented entities. It relies on standard graph-theoretic characterizations and on previously published lower-bound results for EPG bend numbers, all properly cited.

assumptions (4)
  • standard math A graph is outerplanar if and only if adding a new universal vertex v0 yields a planar graph.
    Used in Observation 2.1 to justify Algorithm 2.1's nice labeling; standard characterization cited to [18].
  • domain assumption The nice labeling produced by Algorithm 2.1 satisfies the path separation property.
    Proved in Lemma 2.5, but the proof relies on the planar embedding of G' and the counterclockwise ordering; if this fails, the main algorithm's correctness collapses.
  • standard math Lower-bound results: S3 is not in B0 nor Bm1, and S_n for n >= 4 is not in B1.
    Taken as black boxes from Golumbic et al. [23], Cameron et al. [14], and Heldt et al. [24]; used to establish tightness of the new upper bounds and to drive forbidden-subgraph characterizations.
  • standard math B0-EPG graphs are exactly interval graphs.
    Stated in the introduction as known from Booth and Lueker [10]; used to justify the cactus B0 characterization via interval graphs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid." pith.science (2026). https://pith.science/paper/FPBK557X

@misc{pith2026190801981,
  author       = {Pith},
  title        = {Pith review of: Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FPBK557X}},
  note         = {Machine review of arXiv:1908.01981}
}
abstract

In a representation of a graph $G$ as an edge intersection graph of paths on a grid (EPG) every vertex of $G$ is represented by a path on a grid and two paths share a grid edge iff the corresponding vertices are adjacent. In a monotonic EPG representation every path on the grid is ascending in both rows and columns. In a (monotonic) $B_k$-EPG representation every path on the grid has at most $k$ bends. The (monotonic) bend number $b(G)$ ($b^m(G)$) of a graph $G$ is the smallest natural number $k$ for which there exists a (monotonic) $B_k$-EPG representation of $G$. In this paper we deal with the monotonic bend number of outerplanar graphs and show that $b^m(G)\leqslant 2$ holds for every outerplanar graph $G$. Moreover, we characterize the maximal outerplanar graphs and the cacti with (monotonic) bend number equal to $0$, $1$ and $2$ in terms of forbidden induced subgraphs. As a byproduct we obtain low-degree polynomial time algorithms to construct (monotonic) EPG representations with the smallest possible number of bends for maximal outerplanar graphs and cacti.

Figures

Figures reproduced from arXiv: 1908.01981 by the authors.

Figure 1
Figure 1. The constructions of the subroutine Explore of Algorithm 2.2. Next we observe that whenever we start to explore a new vertex vi in line 11 of Algorithm 2.2 all paths Pv that correspond to a green vertex v have a free part Rv on their lower horizontal segment, in which no other path has been constructed so far. Furthermore these free parts are located in the grid in such a way that if vk and vj are two green vertices… view at source ↗
Figure 2
Figure 2. The graph S3. Now let us turn to the n-sun Sn. The following result holds. Lemma 3.7 (Golumbic, Lipshteyn and Stern [24]). The graph Sn is not in B1 for every n > 4. Next we show that Sn is in Bm 2 for any n > 3. Theorem 3.8. The n-sun Sn is in Bm 2 for all n > 3. Proof. The proof is done by giving a Bm 2 -EPG representation of Sn for any n > 3. Such a representation is depicted in [PITH_FULL_IMAGE:figures/full_fig… view at source ↗
Figure 3
Figure 3. (a) The graph Sn. (b) A Bm 2 -EPG representation of Sn. Notice that the Bm 2 -representation of Sn given in the proof of Theorem 3.8 can be constructed in linear time with respect to n. Summarizing the results of Lemma 3.4, Lemma 3.5, Lemma 3.7 and Theorem 3.8 we obtain the fol￾lowing equalities. Corollary 3.9. The (monotonic) bend number of Sn, n > 3, is given as follows. b(Sn) =  1 for n = 3 2 for n > 4 and b m(S… view at source ↗
Figures from the paper (9 more)
Figure 4
Figure 4. Figure 4: (a) A graph G and its almost-dual Gb with the vertices vˆi for 1 6 i 6 7. (b) A B0-EPG representation of G constructed by Algorithm 4.1. 4.2 Maximal Outerplanar Graphs in B1 In this section we characterize the maximal outerplanar graphs which are Bm 1 -EPG and B1-EPG, …
Figure 5
Figure 5. Figure 5: The graph M1. Next we consider some maximal outerplanar graphs which are not B1- EPG. Lemma 4.12. Let G be a maximal outerplanar graph and Ge its reduced graph. If the graph M1 depicted in [PITH_FULL_IMAGE:figures/full_fig_p024_5.png]
Figure 6
Figure 6. Figure 6: The graph Mℓ 1 with ℓ > 0 consecutive triangles between the vertices a1 and b1. For ℓ = 0 there are no vertices c and the vertices a1 and b1 coincide. For all values of ℓ either {a1, a3} or {a2, a4} and either {b1, b3} or {b2, b4} is an edge in Mℓ 1 . clique and due to…
Figure 7
Figure 7. Figure 7: (a) A part of a graph G with Gb and (b), (c) how Algorithm 4.3 constructs the B1-EPG representation of it. Dotted edges may or may not exist. e d a ′ b ′ c (a) Ruˆ Rwˆ Pb ′ Pa ′ Pd (b) [PITH_FULL_IMAGE:figures/full_fig_p040_7.png]
Figure 8
Figure 8. Figure 8: (a) A part of a graph G with Gb and (b) how Algorithm 4.3 con￾structs the B1-EPG representation of it. Dotted edges may or may not exist. have not been constructed yet. thus the algorithm does not construct more than one path per vertex. Summarizing, for each vertex v …
Figure 9
Figure 9. Figure 9: (a) A part of a graph G with Gb and (b) how Algorithm 4.3 con￾structs the B1-EPG representation of it. Dotted edges may or may not exist. (c) The starting construction of Algorithm 4.3. by Algorithm 4.2. Due to Lemma 4.17 each vertex of G is assigned to at most one ver…
Figure 10
Figure 10. Figure 10: (a) The graph M2. (b) The graph M3. The next lemma represents a less obvious result. Lemma 5.5. The graphs M2 and M3 shown in [PITH_FULL_IMAGE:figures/full_fig_p043_10.png]
Figure 11
Figure 11. Figure 11: The B0-EPG representation of the path G′ of Algorithm 5.1. be the set of vertices of G. We show that Algorithm 5.1 can be implemented to run in O(n log(n)) time. Assume that we use a data structure, in which we can access a vertex in constant time and that all neighbo…
Figure 12
Figure 12. Figure 12: The construction of a Bm 1 -EPG representation of a cactus with free parts of the paths. This constructions are used if Rv lies on a horizontal line of Pv. If Rv lies on a vertical line of Pv, then the constructions have to be rotated by 90o clockwise and then be flip…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

  1. [1]

    Liliana Alcón, Flavia Bonomo, Guillermo Durán, Marisa G utierrez, María Pí a Mazzoleni, Bernard Ries and Mario Valencia-Pabon , On the bend number of circular-arc graphs as edge intersection gra phs of paths on a grid , Discrete Appl. Math. 234 (2018), 12–21

  2. [2]

    2, 129–150

    Andrei Asinowski, Elad Cohen, Martin Charles Golumbic, Vincent Limouzy, Marina Lipshteyn and Michal Stern, Vertex intersection graphs of paths on a grid , Journal of Graph Algorithms and Applica- tions 16 (2012), no. 2, 129–150

  3. [3]

    2, 427–440

    Andrei Asinowski and Bernard Ries, Some properties of edge intersection 55 graphs of single-bend paths on a grid , Discrete Mathematics 312 (2012), no. 2, 427–440

  4. [4]

    14, 3174–3180

    Andrei Asinowski and Andrew Suk, Edge intersection graphs of systems of paths on a grid with a bounded number of bends , Discrete Applied Mathematics 157 (2009), no. 14, 3174–3180

  5. [5]

    Sci., vol

    Therese Biedl, Martin Derka, Vida Dujmović and Pat Morin , EPG- representations with small grid-size , Graph drawing and network visu- alization, Lecture Notes in Comput. Sci., vol. 10692, Sprin ger, Cham, 2018, pp. 184–196

  6. [6]

    Therese Biedl and Michal Stern, Edge-intersection graphs of k-bend paths in grids , Computing and Combinatorics, Springer, 2009, pp. 86– 95

  7. [7]

    Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoretical Computer Science 209 (1991), 1–45

    Hans L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoretical Computer Science 209 (1991), 1–45

  8. [8]

    Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoretical Computer Science 209 (1998), no

    Hans L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoretical Computer Science 209 (1998), no. 1–2, 1 – 45

Show all 29 references
  1. [9]

    340 (2017), no

    Flavia Bonomo, María Pí a Mazzoleni and Maya Stein, Clique coloring B1-EPG graphs , Discrete Math. 340 (2017), no. 5, 1008–1011

  2. [10]

    Booth and George S

    Kellogg S. Booth and George S. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tr ee algorithms , Journal of Computer and System Sciences 13 (1976), no. 3, 335–379

  3. [11]

    Bougeret, S

    M. Bougeret, S. Bessy, D. Gonçalves and C. Paul, On independent set on B1-EPG graphs , Approximation and online algorithms, Lecture Notes in Comput. Sci., vol. 9499, Springer, [Cham], 2015, pp. 158– 169

  4. [12]

    Sci., vol

    Nicolas Bousquet and Marc Heinrich, Computing maximum cliques in B2-EPG graphs, Graph-theoretic concepts in computer science, Lecture Notes in Comput. Sci., vol. 10520, Springer, Cham, 2017, pp. 140–152

  5. [13]

    Brady and M

    M.L. Brady and M. Sarrafzadeh, Stretching a knock-knee layout for mul- tilayer wiring , IEEE Transactions on Computers 39 (1990), no. 1, 148– 151

  6. [14]

    Kathie Cameron, Steven Chaplick and Chính T Hoàng, Edge inter- section graphs of L-shaped paths in grids , Electronic Notes in Discrete Mathematics 44 (2013), 363–369. 56

  7. [15]

    Elad Cohen, Martin Charles Golumbic and Bernard Ries, Characteri- zations of cographs as intersection graphs of paths on a grid , Discrete Appl. Math. 178 (2014), 46–57

  8. [16]

    Sci., vol

    Zakir Deniz, Simon Nivelle, Bernard Ries and David Schi ndl, On split B1-EPG graphs , LATIN 2018: Theoretical informatics, Lecture Notes in Comput. Sci., vol. 10807, Springer, Cham, 2018, pp. 361–3 75

  9. [17]

    Dror Epstein, Martin Charles Golumbic and Gila Morgens tern, Approxi- mation algorithms for B1-EPG graphs, Algorithms and Data Structures, Springer, 2013, pp. 328–340

  10. [18]

    Vieweg & Sohn, Wiesbaden, 2004, Som e chap- ters from combinatorial geometry

    Stefan Felsner, Geometric graphs and arrangements , Advanced Lectures in Mathematics, Friedr. Vieweg & Sohn, Wiesbaden, 2004, Som e chap- ters from combinatorial geometry. MR 2061507

  11. [19]

    Francis and Abhiruk Lahiri, VPG and EPG bend-numbers of Halin graphs , Discrete Appl

    Mathew C. Francis and Abhiruk Lahiri, VPG and EPG bend-numbers of Halin graphs , Discrete Appl. Math. 215 (2016), 95–105

  12. [20]

    3, 211 – 227

    Fănică Gavril, A recognition algorithm for the intersection graphs of paths in trees , Discrete Mathematics 23 (1978), no. 3, 211 – 227

  13. [21]

    Jamison, Edge and vertex in- tersection of paths in a tree , Discrete Mathematics 55 (1985), no

    Martin Charles Golumbic and Robert E. Jamison, Edge and vertex in- tersection of paths in a tree , Discrete Mathematics 55 (1985), no. 2, 151 – 159

  14. [22]

    1, 8 – 22

    , The edge intersection graphs of paths in a tree , Journal of Com- binatorial Theory, Series B 38 (1985), no. 1, 8 – 22

  15. [23]

    3, 130–138

    Martin Charles Golumbic, Marina Lipshteyn and Michal S tern, Edge intersection graphs of single bend paths on a grid , Networks 54 (2009), no. 3, 130–138

  16. [24]

    Edge intersection graphs of single b end paths on a grid

    , Single bend paths on a grid have strong helly number 4: errata atque emendationes ad “Edge intersection graphs of single b end paths on a grid” , Networks 62 (2013), no. 2, 161–163

  17. [25]

    Daniel Heldt, Kolja Knauer and Torsten Ueckerdt, On the bend-number of planar and outerplanar graphs , LATIN 2012: Theoretical Informatics, Springer, 2012, pp. 458–469

  18. [26]

    0, 144 – 162

    Daniel Heldt, Kolja Knauer and Torsten Ueckerdt, Edge-intersection graphs of grid paths: The bend-number , Discrete Applied Mathematics 167 (2014), no. 0, 144 – 162. 57

  19. [27]

    Kocay and Donald L

    William L. Kocay and Donald L. Kreher, Graphs, algorithms and op- timization, Discrete mathematics and its applications, Chapman and Hall/CRC, 2016, 2 edition

  20. [28]

    Paul Molitor, A survey on wiring , J. Inf. Process. Cybern. 27 (1991), no. 1, 3–19

  21. [29]

    Sci., vol

    Martin Pergel and Paweł Rzążewski, On edge intersection graphs of paths with 2 bends , Graph-theoretic concepts in computer science, Lec- ture Notes in Comput. Sci., vol. 9941, Springer, Berlin, 201 6, pp. 207– 219. 58

Pith tools

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