pith. machine review for the scientific record. sign in

arxiv: 2605.12253 · v1 · submitted 2026-05-12 · 🧮 math.CO · cs.CG

Recognition: 2 theorem links

· Lean Theorem

Two Results on Outer-String Graphs

Jan Kratochv\'il, Peter Stumpf, Todor Anti\'c, V\'it Jel\'inek

Pith reviewed 2026-05-13 03:56 UTC · model grok-4.3

classification 🧮 math.CO cs.CG
keywords outer-string graphsouter-k-string representationsNP-hardnesspolynomial-time algorithmsforbidden configurationsconstrained representationsbipartite graphsC3 C5-free graphs
0
0 comments X

The pith

Recognizing whether a graph has an outer-k-string representation 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 on graphs whose vertices are curves inside a disk with one endpoint fixed on the boundary. It proves NP-hardness for deciding the existence of an outer-k-string representation, where any two curves cross at most k times, answering an open question for the k=1 case. In the other direction, when vertices come with a prescribed cyclic order and the graph has no triangles or pentagons, the constrained version of the problem admits a polynomial-time algorithm derived from a characterization by a single forbidden configuration. Together the results separate tractable ordered cases from the general recognition task.

Core claim

For every fixed integer k at least 1, deciding whether a given graph admits an outer-k-string representation is NP-hard. Separately, for any {C3,C5}-free graph equipped with a cyclic order on its vertices, the existence of a constrained outer-string representation can be decided in polynomial time because such representations are exactly the graphs that avoid one specific forbidden configuration.

What carries the argument

The single forbidden configuration that exactly characterizes constrained outer-string representability for {C3,C5}-free graphs under a fixed cyclic anchor order, together with the reduction establishing NP-hardness of the unrestricted outer-k-string problem.

If this is right

  • Outer-k-string recognition stays NP-hard no matter how large the fixed crossing bound k becomes.
  • Constrained outer-string representations become tractable precisely when the input is {C3,C5}-free and the anchor order is supplied.
  • The forbidden-configuration test yields an explicit certificate of non-representability for the constrained case.
  • General outer-string representations without a crossing bound or order constraint remain outside the polynomial-time regime for the classes studied.

Where Pith is reading between the lines

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

  • The hardness result implies that practical layout tools for disk-based string drawings will require heuristics or exponential-time methods on arbitrary instances.
  • The characterization may extend to other intersection models once a suitable forbidden configuration is identified for those models.
  • Applications that already fix an angular order around a circle, such as certain map or circuit drawings, can now use the polynomial algorithm directly.

Load-bearing premise

The single forbidden configuration fully characterizes the constrained outer-string representable {C3,C5}-free graphs with given cyclic order, allowing the polynomial-time decision procedure.

What would settle it

A graph that is {C3,C5}-free, satisfies the given cyclic order, contains the forbidden configuration, yet still possesses a constrained outer-string representation, or a polynomial-time algorithm for outer-1-string recognition.

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

0 major / 2 minor

Summary. The paper establishes two results on outer-string representations. For {C3,C5}-free graphs (including bipartite graphs) equipped with a prescribed cyclic vertex order, it gives a polynomial-time decision procedure for the existence of a constrained outer-string representation, obtained from a characterization by a single forbidden configuration. It also 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 of Biedl et al. (GD 2024).

Significance. If the characterization and the reduction are correct, the results advance the algorithmic and complexity-theoretic understanding of string graphs with boundary anchors. The polynomial-time algorithm supplies an efficient, forbidden-configuration-based method for a natural constrained variant on a broad hereditary class, while the NP-hardness statements demonstrate that bounded-crossing outer-string recognition remains intractable even for constant k. Both contributions rely on standard, verifiable techniques (direct case analysis on cyclic orders and gadget constructions that preserve intersection properties) and directly resolve a stated open problem.

minor comments (2)
  1. [Abstract] The abstract and introduction would benefit from an explicit statement of the open question from Biedl et al. that is being resolved, including a one-sentence paraphrase of the prior result.
  2. [Section 2] Notation for the anchor points and the cyclic order should be introduced once in a dedicated preliminary subsection rather than inline in the first theorem statement.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and for recommending minor revision. The referee's summary accurately captures both of our main contributions: the polynomial-time algorithm for constrained outer-string representations of {C3,C5}-free graphs via a forbidden-configuration characterization, and the NP-hardness proof for outer-k-string recognition for every fixed k ≥ 1, which resolves the open question posed by Biedl et al. (GD 2024). No specific major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity; results are self-contained proofs

full rationale

The paper establishes two independent results: (1) a polynomial-time algorithm for constrained outer-string recognition on {C3,C5}-free graphs, derived from an explicit single-forbidden-configuration characterization proven by direct case analysis on cyclic orders, and (2) NP-hardness of outer-k-string recognition via a gadget-based reduction from a known hard problem. Neither step reduces to a self-definition, fitted parameter renamed as prediction, or load-bearing self-citation; the similarity note to Biedl et al. is non-essential, and the open-question reference is answered with new constructions. All claims rest on internally verifiable combinatorial arguments without circular dependencies.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on standard graph-theoretic assumptions and complexity theory; no new free parameters, axioms beyond background mathematics, or invented entities are introduced.

axioms (1)
  • standard math Standard assumptions of computational complexity theory, including that P is not equal to NP for interpreting hardness results.
    Implicit in all NP-hardness statements.

pith-pipeline@v0.9.0 · 5582 in / 1225 out tokens · 94352 ms · 2026-05-13T03:56:56.969343+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

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