pith. sign in

arxiv: 2605.12253 · v2 · pith:3NQQBV4Ynew · submitted 2026-05-12 · 🧮 math.CO · cs.CG

Two Results on Outer-String Graphs

Todor Anti\'c , V\'it Jel\'inek , Jan Kratochv\'il , Peter Stumpf This is my paper

Pith reviewed 2026-05-19 17:29 UTC · model grok-4.3

classification 🧮 math.CO cs.CG
keywords outer-string graphsconstrained representationsforbidden configurationNP-hardnessbipartite graphsstring intersection graphsgraph representations
0
0 comments X

The pith

Bipartite graphs with a given cyclic order admit a polynomial-time test for constrained outer-string representations based on a single forbidden configuration, while recognizing outer-k-string representations is NP-hard for any fixed k.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes two results about outer-string representations, where vertices appear as curves inside a disk with one endpoint on the boundary. For bipartite graphs and more generally for any {C3, C5}-free graph equipped with a cyclic vertex order, the authors give a polynomial-time algorithm that decides whether a constrained outer-string representation exists. The algorithm rests on a complete characterization by a single forbidden configuration. In the second result, the paper proves that recognizing outer-1-string representations is NP-hard and extends the hardness to outer-k-string representations for every fixed positive integer k.

Core claim

For a bipartite graph G (and more generally for any {C3,C5}-free graph G) with a given cyclic order of vertices, we can decide in polynomial time whether G admits a constrained outer-string representation. Our algorithm follows from a characterization by a single forbidden configuration, similar to that of Biedl et al. [GD 2024] for chordal graphs. We also show that determining whether a given graph admits an outer-1-string representation is NP-hard, and more generally that it is NP-hard to determine if a given graph G admits an outer-k-string representation for any fixed k ≥ 1.

What carries the argument

The single forbidden configuration that completely characterizes which {C3,C5}-free graphs with prescribed cyclic order admit constrained outer-string representations.

If this is right

  • Constrained outer-string representations of bipartite graphs become decidable in polynomial time when a cyclic order is supplied.
  • The same polynomial-time test applies to the larger class of all {C3,C5}-free graphs.
  • Recognizing outer-k-string representations remains NP-hard even when the number of crossings between any pair is bounded by a fixed constant.
  • The single-configuration characterization answers an open question posed for the outer-1-string case.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The forbidden-configuration method may extend to other restricted families of string graphs beyond {C3,C5}-free graphs.
  • Practical drawing algorithms for anchored curve representations could be built directly from the polynomial-time test.
  • Because hardness holds for every fixed k, limiting the number of crossings does not appear to make recognition tractable.

Load-bearing premise

Avoiding one specific forbidden configuration is necessary and sufficient for a {C3,C5}-free graph with given cyclic order to have a constrained outer-string representation.

What would settle it

A {C3,C5}-free graph together with a cyclic order that avoids the forbidden configuration yet has no constrained outer-string representation, or that contains the configuration yet does have such a representation.

read the original abstract

An \emph{outer-string representation} of a graph $G$ is an intersection representation of $G$ where vertices are represented by curves (strings) inside the unit disk and each curve has exactly one endpoint on the boundary of the unit disk (the anchor of the curve). Additionally, if each two curves are allowed to cross at most once, we call this an \emph{outer-$1$-string representation} of $G$. If we impose a cyclic ordering on the vertices of $G$ and require the cyclic order of the anchors to respect this cyclic order, such a representation is called a \emph{constrained outer-string representation}. In this paper, we present two results about graphs admitting outer-string representations. Firstly, we show that for a bipartite graph $G$ (and, more generally, for any $\{C_3,C_5\}$-free graph $G$) with a given cyclic order of vertices, we can decide in polynomial time whether $G$ admits a constrained outer-string representation. Our algorithm follows from a characterization by a single forbidden configuration, similar to that of Biedl et al. [GD 2024] for chordal graphs. Secondly, we answer an open question from the same authors and show that determining whether a given graph admits an outer-1-string representation is NP-hard. More generally, we show that it is NP-hard to determine if a given graph $G$ admits an outer-$k$-string representation for any fixed $k\ge1$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript presents two results on outer-string representations. First, for any {C3,C5}-free graph G equipped with a prescribed cyclic order on its vertices, it gives a polynomial-time algorithm to decide whether G admits a constrained outer-string representation; the algorithm rests on a characterization by the absence of a single forbidden configuration, analogous to the chordal-graph case of Biedl et al. (GD 2024). Second, it proves that recognizing whether an arbitrary graph admits an outer-1-string representation is NP-hard, and extends the hardness to outer-k-string representations for every fixed k ≥ 1, thereby answering an open question posed by the same authors.

Significance. If the characterization is correct, the first result supplies a concrete structural description that yields an efficient recognition procedure for a natural subclass of outer-string graphs and mirrors known results for chordal graphs. The NP-hardness result resolves an explicit open problem and delineates the computational complexity of outer-string recognition problems. The paper therefore contributes both a positive algorithmic result and a matching hardness classification within the study of geometric graph representations.

major comments (1)
  1. [§3] §3 (Characterization theorem): the proof that absence of the single forbidden configuration is sufficient for the existence of a constrained outer-string representation must be checked for the {C3,C5}-free case; the reduction sketched from the chordal setting appears to rely on additional properties of the cyclic order that are not explicitly verified in the argument.
minor comments (2)
  1. [Abstract] The abstract and introduction should state the precise definition of the forbidden configuration (or give a figure reference) rather than only alluding to its existence.
  2. [§2] Notation for the anchor points and the cyclic order should be introduced once in §2 and used consistently thereafter; several later paragraphs re-define the same symbols.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive evaluation and the recommendation of minor revision. We address the single major comment below.

read point-by-point responses

  1. Referee: [§3] §3 (Characterization theorem): the proof that absence of the single forbidden configuration is sufficient for the existence of a constrained outer-string representation must be checked for the {C3,C5}-free case; the reduction sketched from the chordal setting appears to rely on additional properties of the cyclic order that are not explicitly verified in the argument.

    Authors: We agree that the sufficiency direction of the characterization requires explicit verification when moving from chordal graphs to the {C3,C5}-free case. The current manuscript sketches the adaptation from Biedl et al. (GD 2024) but does not spell out every cyclic-order invariant. In the revision we will expand Section 3 with a self-contained argument: we first recall the chordal proof, then verify that every step (anchor ordering, non-crossing constraints, and intersection detection) remains valid under the additional hypothesis that G is {C3,C5}-free. Because the forbidden configuration is defined purely in terms of the prescribed cyclic order and the intersection graph, the absence of triangles and pentagons eliminates precisely the configurations that could otherwise violate the order-preserving properties; no new obstructions arise. The revised proof will therefore confirm that absence of the single forbidden configuration is indeed sufficient. revision: yes

Circularity Check

0 steps flagged

No significant circularity; results are independently derived

full rationale

The paper derives its polynomial-time algorithm from a new characterization of constrained outer-string representations for {C3,C5}-free graphs via a single forbidden configuration, presented as original work that is merely analogous to the unrelated Biedl et al. (GD 2024) result on chordal graphs. The NP-hardness proof for outer-k-string representations resolves an open question from prior literature without depending on any self-citation chain, fitted inputs, or definitional reductions. All load-bearing steps are self-contained within the manuscript's own proofs and do not reduce to the inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The results rest on standard definitions of string graphs and intersection representations together with the assumption that the forbidden-configuration characterization is both correct and sufficient.

axioms (1)
  • standard math Standard definitions of intersection graphs, curves in the plane, and polynomial-time decidability of graph properties.
    Invoked throughout the abstract when stating the decision problem and complexity claims.

pith-pipeline@v0.9.0 · 5813 in / 1201 out tokens · 34648 ms · 2026-05-19T17:29:51.816601+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [1]

    Iqbal Hossain and Stephen G

    Abu Reyan Ahmed and Felice De Luca and Sabin Devkota and Alon Efrat and Md. Iqbal Hossain and Stephen G. Kobourov and Jixian Li and Sammi Abida Salma and Eric Welch , title =. CoRR , volume =. 2017 , url =

    work page 2017

  2. [2]

    Cyclic ordering is

    Zvi Galil and Nimrod Megiddo , abstract =. Cyclic ordering is. Theoretical Computer Science , volume =. 1977 , issn =. doi:https://doi.org/10.1016/0304-3975(77)90005-6 , url =

    work page doi:10.1016/0304-3975(77)90005-6 1977

  3. [3]

    On Grounded

    V. On Grounded. Electron. J. Comb. , volume =. 2019 , OPTurl =

    work page 2019

  4. [4]

    Constrained Outer-String Representations , booktitle =

    Therese Biedl and Sabine Cornelsen and Jan Kratochv. Constrained Outer-String Representations , booktitle =. 2024 , OPTurl =

    work page 2024

  5. [5]

    Constrained Outer-String Representations , journal =

    Therese Biedl and Sabine Cornelsen and Jan Kratochv. Constrained Outer-String Representations , journal =. 2026 , doi =

    work page 2026

  6. [6]

    String graphs

    Jan Kratochv. String graphs. J. Comb. Theory. 1991 , url =. doi:10.1016/0095-8956(91)90091-W , timestamp =

    work page doi:10.1016/0095-8956(91)90091-w 1991

  7. [7]

    1999 , doi =

    Brandst. 1999 , doi =

    work page 1999

  8. [8]

    Matthias Middendorf and Frank Pfeiffer , title =. Discret. Math. , volume =. 1993 , url =. doi:10.1016/0012-365X(93)90176-T , timestamp =

    work page doi:10.1016/0012-365x(93)90176-t 1993

  9. [9]

    String graphs requiring exponential representations , journal =

    Jan Kratochv. String graphs requiring exponential representations , journal =. 1991 , url =. doi:10.1016/0095-8956(91)90050-T , timestamp =

    work page doi:10.1016/0095-8956(91)90050-t 1991

  10. [10]

    and McMorris, F

    McKee, Terry A. and McMorris, F. R. , title =

    work page

  11. [11]

    Kotzig , Fullauthor =

    A. Kotzig , Fullauthor =. Eulerian lines in finite 4-valent graphs and their transformations , Sbooktitle =. Theory of Graphs, Proceedings of the Colloqium held at Tihany (Hungary), Sept.\ 1966 , XXpublisher =

    work page 1966

  12. [12]

    Journal of Combinatorial Theory Ser

    Fanica Gavril , title =. Journal of Combinatorial Theory Ser. B , year = 1974, volume = 16, pages =. doi:10.1016/0095-8956(74)90094-X

    work page doi:10.1016/0095-8956(74)90094-x 1974

  13. [13]

    1976 , doi =

    Intersection graphs of curves in the plane , journal =. 1976 , doi =

    work page 1976

  14. [14]

    Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg , volume = 25, pages =

    On rigid circuit graphs , author =. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg , volume = 25, pages =

    work page

  15. [15]

    Journal of Graph Theory , volume =

    Representations of chordal graphs as subtrees of a tree , author =. Journal of Graph Theory , volume =. 1978 , doi =

    work page 1978

  16. [16]

    Martin Charles Golumbic , title =

    work page

  17. [17]

    On the chromatic number of disjointness graphs of curves , journal =

    J. On the chromatic number of disjointness graphs of curves , journal =. 2020 , doi =

    work page 2020

  18. [18]

    James Davies and Tomasz Krawczyk and Rose McCarty and Bartosz Walczak , title =. Discret. Comput. Geom. , volume =. 2023 , doi =

    work page 2023

  19. [19]

    F. W. Sinden. Topology of thin film RC circuits. Bell System Tech. J. 1966 , doi =

    work page 1966

  20. [20]

    16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT'18) , editor =

    Therese Biedl and Ahmad Biniaz and Martin Derka , title =. 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT'18) , editor =. 2018 , doi =

    work page 2018

  21. [21]

    International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'17) , editor =

    Therese Biedl and Martin Derka , title =. International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'17) , editor =. 2017 , doi =

    work page 2017

  22. [22]

    2019 , url =

    Alexandre Rok and Bartosz Walczak , title =. 2019 , url =. doi:10.1137/17M1157374 , timestamp =

    work page doi:10.1137/17m1157374 2019

  23. [23]

    Trotter , title =

    Cornelia Dangelmayr and Stefan Felsner and William T. Trotter , title =. J. Graph Algorithms Appl. , volume =. 2010 , OPTurl =

    work page 2010

  24. [24]

    1986 , publisher=

    String Graphs , author=. 1986 , publisher=

    work page 1986

  25. [25]

    String graphs , booktitle=

    Jan Kratochv. String graphs , booktitle=

    work page

  26. [26]

    Sean McGuinness , title =. Discret. Math. , volume =. 1996 , OPTurl =

    work page 1996

  27. [27]

    Recognizing string graphs in

    Marcus Schaefer and Eric Sedgwick and Daniel. Recognizing string graphs in. J. Comput. Syst. Sci. , volume =. 2003 , url =. doi:10.1016/S0022-0000(03)00045-X , timestamp =

    work page doi:10.1016/s0022-0000(03)00045-x 2003

  28. [28]

    Mathias Middendorf and Frank Pfeiffer , title =. Discret. Math. , volume =. 1992 , doi =

    work page 1992

  29. [29]

    Trotter and Bartosz Walczak , title =

    Arkadiusz Pawlik and Jakub Kozik and Tomasz Krawczyk and Michal Lason and Piotr Micek and William T. Trotter and Bartosz Walczak , title =. J. Comb. Theory, Ser. 2014 , doi =

    work page 2014

  30. [30]

    Schaefer , editor =

    Thomas J. Schaefer , editor =. The Complexity of Satisfiability Problems , booktitle =. 1978 , doi =

    work page 1978

  31. [31]

    Dichotomy for orderings? , booktitle =

    G. Dichotomy for orderings? , booktitle =. 2026 , doi =

    work page 2026