Pith. sign in

REVIEW 3 major objections 3 minor 45 references

On Strict (Outer-)Confluent Graphs

T0 review · 3 major / 3 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 places strict confluent graphs inside string graphs and unit-interval graphs inside strict confluent graphs.

desk verdict First substantial structural results for strict (outer-)confluent graphs, but the unit-interval inclusion has a definitional gap with Δ-junctions that needs patching. read the letter →

arxiv 1908.05345 v1 pith:CAQMJHWN submitted 2019-08-14 cs.CG cs.DMmath.CO

Henry Förster , Robert Ganian , Fabian Klute , Martin Nöllenburg This is my paper · ORCID
classification cs.CGcs.DMmath.CO MSC 05C6205C7568R1068U05
keywords strictconfluentgraphsouterconfluentstringouter-stringunit-intervalbipartitepermutationclique-widthcopnumber
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

This paper studies strict confluent graph drawings, in which edges are not drawn as individual curves but as unique smooth paths through a planar network of junctions and arcs. It establishes that the class of strict confluent (SC) graphs is contained in the class of string graphs, and the class of strict outerconfluent (SOC) graphs is contained in the class of outer-string graphs. Conversely, it shows that every unit-interval graph has a strict confluent drawing. It also gives the first exact characterization of a natural strict outerconfluent class: the strict bipartite-outerconfluent graphs are exactly the domino-free bipartite permutation graphs. On the algorithmic side, the paper proves that SOC graphs have cop number at most two and that tree-like strict outerconfluent drawings with $\Delta$-junctions have clique-width at most 16, making these graphs accessible to algorithms for bounded clique-width and to cops-and-robbers analysis.

What carries the argument

The central objects are junction trees and traces. For each vertex $u$, the junction tree $T_u$ has root $u$, leaves at the neighbors of $u$, and internal vertices at the junctions on the unique $uv$-paths; strictness makes this a tree. The trace $t(u)$ is a single curve obtained by a left-first DFS traversal of $T_u$, with U-turns at leaves and rerouting at shared merge-junctions; traces intersect if and only if the corresponding vertices are adjacent. This carries Theorems 1 and 2. For Theorem 3, the key gadget is a clique layout using $\Delta$-junctions and split-junctions that route arcs between consecutive cliques across a line $H$ to invert order. For Theorem 5, the mechanism is the merge-split pair and the observation that in the cyclic order every crossing must be representable as part of a $K_{2,2}$; non-representable crossings in alternating $K_{3,3}$ order and in domino order are the obstructions. For Theorem 6, the central object is the node interval $N[u,v]$ between two vertices on the outer face, together with extremal pairs that allow cops to shrink the robber's locked interval. For Theorem 7, the mechanism is a region decomposition of the outer face: each region is outerplanar (clique-width at most 5), and the regions are glued together by a 16-expression using special labels for border vertices.

What would settle it

Inspect the clique gadget in the proof of Theorem 3: for a clique of three vertices, the three incident arcs meet smoothly at a $\Delta$-junction. Check whether this gadget can be converted into a sequence of binary merge/split junctions while preserving the property that each pair of vertices has exactly one smooth path. If no such conversion exists for some unit-interval graph (for instance, the smallest graph whose construction requires a $\Delta$-junction), then the claimed inclusion of unit-interval graphs into SC would not be supported by the paper's construction, and one should search for a concrete unit-interval graph that admits no strict confluent drawing.

Watch

Extended reading notes

Core claim

The paper claims that strict confluent graphs form a subclass of string graphs (Theorem 1) and strict outerconfluent graphs form a subclass of outer-string graphs (Theorem 2). The mechanism is a tracing argument: from each vertex, one follows its junction tree and lays out a single curve that intersects another trace exactly when the two vertices are adjacent. The paper also claims that unit-interval graphs are strict confluent (Theorem 3), via a decomposition into cliques of consecutive intervals and explicit confluent gadgets for edges between neighboring cliques. For the outerconfluent setting, the paper claims that the class of strict bipartite-outerconfluent graphs equals the class of bipartite permutation graphs that are domino-free (Theorem 5), thereby giving the first exact characterization of a strict outerconfluent graph class; the proof shows that any non-strict bipartite outerconfluent drawing forces a chorded 6-cycle, which in a bipartite permutation graph is a $K_{3,3}$ (minus an edge) that can be redrawn strictly, and conversely that the domino obstruction is the only obstacle. Finally, the paper claims that every strict outerconfluent graph has cop number at most two (Theorem 6) by an interval-shrinking argument on the cyclic order of vertices, and that tree-like strict outerconfluent drawings with $\Delta$-junctions have clique-width at most 16 (Theorem 7) by a decomposition into regions that each have clique-width at most 5, combined using labeled expressions.

Load-bearing premise

The proof that every unit-interval graph is strict confluent uses three-way junctions that smoothly connect three arcs; the paper's official definition of strict confluent drawings allows only binary merge/split junctions, and no argument is given that these three-way junctions can be replaced by binary ones without creating two smooth paths between some pair of vertices.

Editorial extensions

If this is right

  • Every unit-interval graph inherits all properties of strict confluent graphs, and every strict confluent graph inherits all properties of string graphs; in particular, any lower bound or algorithmic result known for string graphs applies to these classes.
  • The exact equality of strict bipartite-outerconfluent graphs with domino-free bipartite permutation graphs means this class is polynomial-time recognizable: one can compute a bipartite permutation representation and test the domino-free condition.
  • The cop-number bound of at most two puts SOC graphs on the same footing as interval-filament graphs among subclasses of outer-string graphs, and suggests that a single additional structural property separates them.
  • The clique-width bound of 16 for tree-like $\Delta$-SOC graphs makes these graphs amenable to fixed-parameter algorithms and to meta-theorems for problems expressible in monadic second-order logic on graphs.
  • The non-inclusion results for circle, circular-arc, chordal, co-chordal, comparability, co-comparability, series-parallel, and pseudo-split graphs show that SOC graphs do not collapse into any of these standard families, so they form a genuinely new intersection-related class.

Reading between the lines

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

  • The trace construction in Section 3 uses strictness mainly to ensure junction trees are trees; for non-strict confluent drawings, a similar construction might produce intersection representations by multi-curves or families of curves, possibly placing all confluent graphs inside a known intersection class such as multistring graphs.
  • The interval-shrinking proof of the cop-number bound may be adaptable to show that SOC graphs are contained in interval-filament graphs, a question the authors leave open; if so, SOC graphs would inherit further algorithmic and structural properties of that class.
  • The exact characterization of strict bipartite-outerconfluent graphs suggests a route toward a full characterization of all SOC graphs: the domino and alternating-$K_{3,3}$ obstructions could serve as the seeds of a split-decomposition or modular-decomposition tree characterization, which the authors mention as a promising but unexplored direction.
  • The clique-width bound of 16 is likely not tight: the constant arises from a generic labeling lemma applied to outerplanar regions, and a finer analysis of how regions interact at junctions could lower the bound or identify which labels can be reused.
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

3 major / 3 minor

Summary. The paper studies strict confluent (SC) and strict outerconfluent (SOC) graph drawings, in which edges are represented by unique smooth paths through a planar system of arcs and junctions. The main contributions are: (1) every SC graph is a string graph and every SOC graph is an outer-string graph (Theorems 1 and 2); (2) every unit-interval graph admits an SC drawing (Theorem 3); (3) the strict bipartite-outerconfluent graphs are exactly the domino-free bipartite permutation graphs (Theorem 5); (4) SOC graphs have cop number two (Theorem 6); and (5) tree-like Δ-SOC graphs have clique-width at most 16 (Theorem 7). The appendix also contains incomparability results between SOC graphs and several other graph classes. The paper is well structured, with detailed appendix proofs for most theorems, and it provides explicit geometric constructions for several of the inclusions.

Significance. If the results hold, the paper gives the first exact characterization of a natural strict outerconfluent graph class and establishes useful algorithmic and structural consequences, particularly the clique-width bound for tree-like Δ-SOC graphs and the cop-number result. The inclusions placing SC and SOC graphs inside string and outer-string graph families are also valuable for future work on recognition and on the relationship to intersection graph classes. The paper's strength lies in its concrete constructions and in the breadth of the graph-class comparisons in Appendix E. The main caveat is that the proof of Theorem 3 uses a junction type that is not part of the strict confluent model as defined in Section 2, and this issue directly affects the paper's central inclusion claim for unit-interval graphs.

major comments (3)
  1. [Section 4 / Appendix B, Theorem 3] The construction of strict confluent diagrams for unit-interval graphs uses Δ-junctions d_i (Appendix B, paragraph beginning 'We draw each clique Ci'), where each Δ-junction 'smoothly links each pair of the three incident arcs.' However, Section 2 defines a junction for strict confluent diagrams as a binary junction with exactly one smooth pair, and Section 7 explicitly introduces Δ-junctions as an additional junction type for a separate tree-like Δ-SOC model. The proof gives no argument that a Δ-junction can be expanded into binary junctions while preserving the exact set of smooth paths and the uniqueness requirement of strictness. Since the clique layout is the core of the construction, the claimed inclusion unit-interval ⊆ SC is not established in the paper's own model unless such a decomposition lemma is supplied or the construction is reworked with binary junctions only.
  2. [Appendix F, Theorem 9 (Section 7)] The induction for the clique-width bound relies on the region-decomposition claim that 'all vertices of group D have precisely the same neighborhood outside of R' and on the assertion that 'at most one vertex, denoted s, in VR3 has two neighbors outside of VR3.' These statements are load-bearing for the 16-expression construction, but they are asserted without proof; the preceding observation that such vertices 'must all have a path to j which forms a smooth curve' does not by itself imply equality of outside neighborhoods. Please provide a formal argument, or weaken the construction accordingly.
  3. [Appendix C, Lemma 2] The proof of Lemma 2 is too terse at a load-bearing point: the 'minimal distinct sub-paths p′ and q′ between two junctions i,j' are not defined formally, and the claim that following the arcs of the two merge-split pairs yields four nodes that together with u and v form a domino subgraph is asserted rather than demonstrated. Since Theorem 5 depends on Lemma 2, this case analysis should be expanded.
minor comments (3)
  1. [Section 2] The sentence 'A (strict) confluent diagram with higher-degree junctions can easily be transformed into an equivalent (strict) one with only binary junctions' is later invoked implicitly, but Δ-junctions are degree-three junctions with three smooth pairs. Please state explicitly whether the transformation applies to Δ-junctions and give a proof or reference.
  2. [Appendix E, Theorem 8] The proof for co-comparability graphs says that a graph is 'verified to not be SOC by exhaustively searching all orders for represented crossings'; the search is not described, so the statement is not independently checkable. Please provide details or a reference.
  3. [Figure 1] The legend refers to 'red, dashed boxes', 'orange boxes', and 'blue boxes', which are not distinguishable in black-and-white print; consider adding symbols or patterns.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central inclusions are argued from the drawing model, and the flagged Δ-junction issue is a proof gap rather than a definitional reduction.

full rationale

The derivation chain is self-contained against external benchmarks. Theorems 1 and 2 construct string and outer-string representations directly from strict confluent diagrams via the trace construction; both directions are argued within the paper and do not quote a result that already contains the theorem. Theorem 3's construction uses Δ-junctions, which are not part of the binary-junction SC model of Section 2; that is an internal proof gap concerning the absence of a decomposition argument, not circularity, because the claimed inclusion is not defined in terms of the construction and no fitted parameter or cited theorem is being renamed as a prediction. Theorem 5 invokes the Hui et al. theorem as an external characterization of bipartite-outerconfluent graphs and then proves strictness via Lemma 2 and Observation 1; the cited theorem does not contain the domino-free strictness condition, so the novel strictness result is genuinely additional. The cop-number theorem and the clique-width bound are argued from the drawing model and from standard external facts such as the clique-width of outerplanar graphs and distance-hereditary graphs, not from the results being proved. The only self-citation is Nöllenburg's coauthorship on Eppstein et al. [14], from which the paper takes the definition of SC/SOC and the binary-junction normalization; that is an independent, parameter-free prior observation and is not used to foreclose alternatives. No equation or fitted parameter is renamed as a prediction, and no claimed result reduces to its own input by construction.

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

No curve fitting and no invented entities appear. The results rely on prior definitions and theorems about confluent drawings, bipartite permutation graphs, clique-width bounds, and on geometric assertions about trace construction and robber locking. The most fragile assumed premise is the silent use of delta-junctions in the proof of Theorem 3.

assumptions (5)
  • domain assumption A strict confluent diagram may be assumed to use only binary junctions, where exactly three arcs meet and two arcs merge into one or split from one.
    Stated in Section 2 as an observation from Eppstein et al. Used throughout the strict constructions; Theorem 3 uses a different junction type that is not covered by this assumption.
  • domain assumption Bipartite-outerconfluent graphs are exactly bipartite permutation graphs (Hui et al., Theorem 4).
    This external characterization is the base for Theorem 5, which adds strictness and domino-freeness on top of it.
  • domain assumption Distance-hereditary graphs have clique-width at most 3 and outerplanar graphs have clique-width at most 5.
    Used in the proof of Theorem 7 to bound the clique-width of the modular regions in the 16-expression construction.
  • domain assumption The trace construction in Section 3 can be performed so that cutting and re-routing traces at shared merge junctions never creates unintended intersections.
    This geometric claim is load-bearing for Theorems 1 and 2; it is illustrated in Figure 3 and argued by cases, but not formally verified.
  • domain assumption The locking behavior described in Lemmas 3 to 5 correctly follows from the geometry of strict outerconfluent drawings.
    The cop number theorem depends on these lemmas, which argue that paths leaving an interval must cross a path of a cop-placed node; the proofs are geometric and appeal to figures.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On Strict (Outer-)Confluent Graphs." pith.science (2026). https://pith.science/paper/CAQMJHWN

@misc{pith2026190805345,
  author       = {Pith},
  title        = {Pith review of: On Strict (Outer-)Confluent Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CAQMJHWN}},
  note         = {Machine review of arXiv:1908.05345}
}
abstract

A strict confluent (SC) graph drawing is a drawing of a graph with vertices as points in the plane, where vertex adjacencies are represented not by individual curves but rather by unique smooth paths through a planar system of junctions and arcs. If all vertices of the graph lie in the outer face of the drawing, the drawing is called a strict outerconfluent (SOC) drawing. SC and SOC graphs were first considered by Eppstein et al. in Graph Drawing 2013. Here, we establish several new relationships between the class of SC graphs and other graph classes, in particular string graphs and unit-interval graphs. Further, we extend earlier results about special bipartite graph classes to the notion of strict outerconfluency, show that SOC graphs have cop number two, and establish that tree-like ($\Delta$-)SOC graphs have bounded cliquewidth.

Figures

Figures reproduced from arXiv: 1908.05345 by the authors.

Figure 1
Figure 1. Inclusions among graph classes related to SOC graphs. Arrows point from [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. A strict outerconfluent diagram representing K5. Nodes are disks, junctions are squares. Let D = (N, J, Γ) be a confluent diagram and let u, v ∈ N be two nodes. A uv-path p = (γ0, . . . , γk) in D is a sequence of arcs γ0 = (u, j1), γ1 = (j1, j2), . . . , γk = (jk, v) ∈ Γ such that j1, . . . jk are junctions and p is a smooth curve. In [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Two possible configurations for in￾serting a new trace t(u) that meets an ex￾isting trace t(v) at a merge junction i; t(v) is cut and re-routed. Finally, at a merge-junction i with at least one trace from the other arc merging into i already drawn: Let v ∈ N such that u and v merge at i and t(v) is already tracing the subtree Tu,i = Tv,i. In this case we temporarily cut open the part of trace t(v) closest to t(u), r… view at source ↗
Figures from the paper (14 more)
Figure 4
Figure 4. Figure 4: (a) A unit interval graph G with a decomposition of its vertices into a set of cliques as described in the proof of Theorem 3; and (b) a strict confluent layout of G computed by the algorithm described in the proof of Theorem 3. We route arcs between cliques Ci and Ci+…
Figure 5
Figure 5. Figure 5: Moves of the cops to confine the robber to a strictly smaller range. [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]
Figure 6
Figure 6. Figure 6: A ∆-confluent diagram representing K5 − (u, v). Nodes are disks, junctions are squares. ∆-junctions are marked with a grey circle. In this section, we lift the result of Epp￾stein et al. [12] to the class of strict out￾erconfluent graphs: in particular, we show that as…
Figure 7
Figure 7. Figure 7: Sketch of a tree-like ∆-SOC graph G with its regions. The second ingredient used in the proof is tied to the tree-like structure of the drawing. In particular, one cannot construct a 16-expression (and even any k-expression for constant k) by simply joining the regions…
Figure 8
Figure 8. Figure 8: Forbidden alternating order of K3,3. u v u v u v w z x y w z x y x w z y [PITH_FULL_IMAGE:figures/full_fig_p018_8.png]
Figure 10
Figure 10. Figure 10: A circular path with only two merge-split pairs can be redrawn without [PITH_FULL_IMAGE:figures/full_fig_p019_10.png]
Figure 11
Figure 11. Figure 11: Redrawing a K3,3 minus an edge. The red edge is missing. Since the graph is bipartite, we find that for every path using one of the green arcs on the left, we can redraw it such that it merges into the path coming from u3 at the green marker without creating any wrong…
Figure 9
Figure 9. Figure 9: Hence there must be at least two merge-split pairs on [PITH_FULL_IMAGE:figures/full_fig_p019_9.png]
Figure 12
Figure 12. Figure 12: Moves of the cops to confine the robber to a strictly smaller range. [PITH_FULL_IMAGE:figures/full_fig_p021_12.png]
Figure 14
Figure 14. Figure 14: Counterexample for SOC ⊆ comparability [PITH_FULL_IMAGE:figures/full_fig_p023_14.png]
Figure 16
Figure 16. Figure 16: The complement of a subdi￾vided star is a counterexample for co￾comparability ⊆ SOC. Function repre￾sentation on the right [25] E Non-Inclusion Results for Strict Outerconfluent Graphs Here we collect smaller results for classes of graphs which have non-empty in￾terse…
Figure 17
Figure 17. Figure 17: Counterexample for SOC ⊆ circle. The light-blue edges give the SOC drawing. Co-comparability graphs are the intersection graphs of x-monotone curves in a vertical strip [25]. The polygon-circle graphs are the graphs which have an intersection model of polygons inscrib…
Figure 18
Figure 18. Figure 18: From left to right: the graphs W5, W7 and BW3 used in Def. 1. a vertex w with edges (u, w) and (w, v). This graph is chordal, but it does not even have a confluent drawing by [9]. Co-chordal. C5 is self-complementary and has a strict outerconfluent draw￾ing, but co-ch…
Figure 19
Figure 19. Figure 19: Sketch of a tree-like ∆-SOC graph G with the regions and junctions used in the inductive construction of the 16-expression defining G. As the first step of our procedure, for each v ∈ Vc we create a 1-expression 1(v) (i.e., we create each vertex in Vc as a singleton).…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

45 extracted references · 45 canonical work pages

  1. [1]

    Discrete Applied Mathe- matics 8(1), 1–12 (1984)

    Aigner, M., Fromme, M.: A game of cops and robbers. Discrete Applied Mathe- matics 8(1), 1–12 (1984)

    work page 1984

  2. [2]

    IEEE Transactions on Visualization and Computer Graphics 23(1), 541–550 (2017)

    Bach, B., Riche, N.H., Hurter, C., Marriott, K., Dwyer, T.: Towards unambiguous edge bundling: Investigating confluent drawings for network visualization. IEEE Transactions on Visualization and Computer Graphics 23(1), 541–550 (2017)

    work page 2017

  3. [3]

    Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153–180 (1994)

    work page 1994

  4. [4]

    Benzaken, C., Crama, Y., Duchet, P., Hammer, P.L., Maffray, F.: More character- izations of triangulated graphs. J. of Graph Theory 14(4), 413–422 (1990)

    work page 1990

  5. [5]

    Bouchet, A.: Circle graph obstructions. J. of Combinatorial Theory, Series B 60(1), 107–144 (1994)

    work page 1994

  6. [6]

    Congressus Numerantium 58, 165–174 (1987)

    Brandst¨ adt, A., Spinrad, J., Stewart, L.: Bipartite permutation graphs are bipartite tolerance graphs. Congressus Numerantium 58, 165–174 (1987)

    work page 1987

  7. [7]

    Theory Comput

    Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization prob- lems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125–150 (2000)

    work page 2000

  8. [8]

    Discrete Applied Mathematics 101(1-3), 77–114 (2000)

    Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Applied Mathematics 101(1-3), 77–114 (2000)

    work page 2000

Show all 45 references
  1. [9]

    Dickerson, M., Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent drawings: Visualizing non-planar diagrams in a planar way. J. Graph Algorithms Appl. 9(1), 31–52 (2005)

    2005

  2. [10]

    Duffin, R.: Topology of series-parallel networks. J. of Mathematical Analysis and Applications 10(2), 303 – 318 (1965)

    1965

  3. [11]

    Ehrlich, G., Even, S., Tarjan, R.E.: Intersection graphs of curves in the plane. J. of Combinatorial Theory, Series B 21(1), 8–20 (1976)

    1976

  4. [12]

    In: Graph Drawing (GD’05)

    Eppstein, D., Goodrich, M.T., Meng, J.Y.: Delta-confluent drawings. In: Graph Drawing (GD’05). LNCS, vol. 3843, pp. 165–176. Springer (2006)

    2006

  5. [13]

    Algorith- mica 47, 439–452 (2007)

    Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent layered drawings. Algorith- mica 47, 439–452 (2007)

    2007

  6. [14]

    Eppstein, D., Holten, D., L¨ offler, M., N¨ ollenburg, M., Speckmann, B., Verbeek, K.: Strict confluent drawing. J. of Computational Geometry 7(1), 22–46 (2016)

    2016

  7. [15]

    Eppstein, D., Simons, J.A.: Confluent Hasse diagrams. J. of Graph Algorithms and Applications 17(7), 689–710 (2013)

    2013

  8. [16]

    Discrete Applied Mathematics 74(1), 13–32 (1997)

    Felsner, S., M¨ uller, R., Wernisch, L.: Trapezoid graphs and generalizations, geom- etry and algorithms. Discrete Applied Mathematics 74(1), 13–32 (1997)

    1997

  9. [17]

    Gabor, C.P., Supowit, K.J., Hsu, W.L.: Recognizing circle graphs in polynomial time. J. ACM 36(3), 435–473 (1989)

    1989

  10. [18]

    Acta Mathematica Hungarica 18(1-2), 25–66 (1967)

    Gallai, T.: Transitiv orientierbare Graphen. Acta Mathematica Hungarica 18(1-2), 25–66 (1967)

    1967

  11. [19]

    In: Algorithms and Computation (ISAAC’13)

    Gavenciak, T., Jel´ ınek, V., Klav´ ık, P., Kratochv´ ıl, J.: Cops and robbers on inter- section graphs. In: Algorithms and Computation (ISAAC’13). pp. 174–184 (2013)

    2013

  12. [20]

    Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum cover- ing by cliques, and maximum independent set of a chordal graph. SIAM J. on Computing 1(2), 180–187 (1972)

    1972

  13. [21]

    Information Processing Letters 73(5-6), 181–188 (2000)

    Gavril, F.: Maximum weight independent sets and cliques in intersection graphs of filaments. Information Processing Letters 73(5-6), 181–188 (2000)

    2000

  14. [22]

    Discrete Ap- plied Mathematics 160(6), 708–733 (2012) 14 Henry F¨ orster, Robert Ganian, Fabian Klute, and Martin N¨ ollenburg

    Gioan, E., Paul, C.: Split decomposition and graph-labelled trees: Characteriza- tions and fully dynamic algorithms for totally decomposable graphs. Discrete Ap- plied Mathematics 160(6), 708–733 (2012) 14 Henry F¨ orster, Robert Ganian, Fabian Klute, and Martin N¨ ollenburg

    2012

  15. [23]

    Golumbic, M.C.: Algorithmic graph theory and perfect graphs, vol. 57. Elsevier (2004)

    2004

  16. [24]

    Discrete Ap- plied Mathematics 9(2), 157–170 (1984)

    Golumbic, M.C., Monma, C.L., Trotter Jr, W.T.: Tolerance graphs. Discrete Ap- plied Mathematics 9(2), 157–170 (1984)

    1984

  17. [25]

    Discrete Mathematics 43(1), 37 – 46 (1983)

    Golumbic, M.C., Rotem, D., Urrutia, J.: Comparability graphs and intersection graphs. Discrete Mathematics 43(1), 37 – 46 (1983)

    1983

  18. [26]

    Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. 11(3), 423–443 (2000)

    2000

  19. [27]

    Courier Corporation (2015)

    Hadwiger, H., Debrunner, H., Klee, V.: Combinatorial geometry in the plane. Courier Corporation (2015)

    2015

  20. [28]

    Hajnal, A., Sur´ anyi, J.: ¨Uber die Aufl¨ osung von Graphen in vollst¨ andige Teil- graphen. Ann. Univ. Sci. Budapest, E¨ otv¨ os Sect. Math1, 113–121 (1958)

    1958

  21. [29]

    In: Graph- Theoretic Concepts in Computer Science (WG’11)

    Halld´ orsson, M.M., Kitaev, S., Pyatkin, A.: Alternation graphs. In: Graph- Theoretic Concepts in Computer Science (WG’11). LNCS, vol. 6986, pp. 191–202. Springer (2011)

    2011

  22. [30]

    IEEE Trans

    Holten, D.: Hierarchical edge bundles: Visualization of adjacency relations in hier- archical data. IEEE Trans. Visualization and Computer Graphics 12(5), 741–748 (2006)

    2006

  23. [31]

    Hsu, W.L.: Maximum weight clique algorithms for circular-arc graphs and circle graphs. SIAM J. on Computing 14(1), 224–231 (1985)

    1985

  24. [32]

    Algorithmica 47(4), 465–479 (2007)

    Hui, P., Pelsmajer, M.J., Schaefer, M., Stefankovic, D.: Train tracks and confluent drawings. Algorithmica 47(4), 465–479 (2007)

    2007

  25. [33]

    Dis- crete Mathematics 163(1-3), 299–305 (1997)

    Kostochka, A., Kratochv´ ıl, J.: Covering and coloring polygon-circle graphs. Dis- crete Mathematics 163(1-3), 299–305 (1997)

    1997

  26. [34]

    Kratochv´ ıl, J.: String graphs. I. the number of critical nonstring graphs is infinite. J. Combinatorial Theory, Series B 52(1), 53–66 (1991)

    1991

  27. [35]

    Canadian Journal of Mathematics 23(1), 160–175 (1971)

    Pnueli, A., Lempel, A., Even, S.: Transitive orientation of graphs and identification of permutation graphs. Canadian Journal of Mathematics 23(1), 160–175 (1971)

    1971

  28. [36]

    Proof techniques in graph theory pp

    Roberts, F.S.: Indifference graphs. Proof techniques in graph theory pp. 139–146 (1969)

    1969

  29. [37]

    Takamizawa, K., Nishizeki, T., Saito, N.: Linear-time computability of combinato- rial problems on series-parallel graphs. J. ACM 29(3), 623–641 (1982)

    1982

  30. [38]

    Trotter, W.T.: Combinatorics and partially ordered sets: Dimension theory, vol. 6. JHU Press (2001)

    2001

  31. [39]

    Wegner, G.: Eigenschaften der Nerven homologisch-einfacher Familien im Rn. Ph.D. thesis, Universit¨ at G¨ ottingen (1967)

    1967

  32. [40]

    right-most

    Yu, C.W., Chen, G.H.: Efficient parallel algorithms for doubly convex-bipartite graphs. Theoretical Computer Science 147(1-2), 249–265 (1995) On Strict (Outer-)Confluent Graphs 15 A Omitted Proofs from Section 3 Lemma 1. LetD = (N,J,Γ ) be a strict confluent diagram, let u,v∈N be ...

    1995

  33. [41]

    relabel labels 1–4 used in the 16-expression for R2 to labels 5–8 and the labels 1–4 used in the 16-expression for R3 to labels 9–12, respectively

  34. [42]

    use the ⊕ operator to merge these 16-expressions,

  35. [43]

    use the ηi,j operator to add edges between VR1∪VR2 and VR3 as required, in particular: η9,2, η11,2, η10,5, η11,5

  36. [44]

    use the η4,8 operator to add all pairwise edges between the groups D ofVR1 and VR2 in case junction j′ smoothly connects arcs a1 and a2

  37. [45]

    Group A coincides with group A ofVR1 and group B coincides with group B of VR2

    use the pi→j operator to relabel as required by the inductive assumption, where depending on the junction type of j′ group D of VR either consist of the union of the groups D ofVR1 andVR2 or it is identical to group D of just one of them. Group A coincides with group A ofVR1 a...

Pith tools

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