CS Paper Radar

Constrained intersection representations and forbidden patterns

Laurent Feuilloley, Michel Habib, Amalia Sorondo

cs.DM math.CO ·submitted 2026-11-12 14:22 UTC · v1

Abstract

We study the interplay between two types of graph classes: the ones defined by intersections of geometric objects and the ones defined by the absence of a substructure. More precisely, we study intersection graphs that are grounded, that is, the objects lie above a horizontal line that they touch, and ordered graphs with forbidden patterns, that is, ordered graphs that avoid a set of ordered induced subgraphs. These two approaches are fundamentally different, but it is known that several interesting graph classes have both types of characterizations, and we aim to understand whether this is a general phenomenon. Our contributions are the following. First, we identify a family of patterns on four vertices and a natural hierarchy of intersection graphs of strings whose classes are nicely interleaved. This raises hopes to prove connections between the two perspectives. Second, we dampen these hopes by proving that a class of (ordered) intersection graphs that we study cannot be characterized by a finite set of forbidden patterns. Third, we show a dual impossibility result: there exists a pattern-defined class of our hierarchy that admits no intersection representation, if we require this representation to be closed under natural operations such as translation and scaling. However, it turns out that if we allow slightly more exotic intersection representations, then we can find one for this pattern-defined class.

Closest papers

Nearest neighbours by meaning across the whole index.

The (Parameterized) Complexity of Ordering a Graph While Avoiding a Forbidden Pattern

cs.DS cs.CC ·2026-08-31 ·Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, Martin Nöllenburg +1 more
published similarity 0.67
Abstract · Appears in the Proceedings of the 21st International Symposium on Parameterized and Exact Computation (IPEC 2026); 57 pages, 11 figures, 1 t…

In this paper, we study the Pattern Avoidance problem of determining whether a given graph $G$ admits a linear vertex order which avoids a given pattern $P$, i.e., a vertex sequence with some forced and forbidden edges, on every suborder. Such patterns form a natural ordered counterpart to induced subgraphs in the order-invariant setting, and it is known that Pattern Avoidance captures a broad variety of graph problems including Bandwidth, Vertex Coloring, Queue Number, and extends to vertex-deletion problems such as Odd Cycle Transversal. We show that Pattern Avoidance is $Σ_2^{\textsf{P}}$-complete and furthermore remains intractable (in both the classical and parameterized sense) even under a variety of severe restrictions to both the pattern $P$ and the graph $G$. As our main contributions, we complement these lower bounds with the following tractability results, which provide a unifying framework for recognizing pattern-definable graph classes: - a fixed-parameter algorithm w.r.t. the vertex integrity of $G$ plus $|V(P)|$, - a fixed-parameter algorithm w.r.t. the neighborhood diversity of $G$ plus $|E(P)|$, and - a polynomial algorithm for Pattern Avoidance on forests for almost all constant-sized patterns.

0.54

Language-Representability: Possibilities and Limitations

cs.FL ·2026-08-25 ·Zhidan Feng, Henning Fernau, Pamela Fleischmann, Kevin Mann, Silas Cato Sacher
published similarity 0.67
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

The study of word-representability was initiated by the seminal work of Kitaev and Pyatkin in 2008 that has later led to the monograph by Kitaev and Lozin in 2015. In this paper, we build on the very recent work by Fernau et al. who proposed a general framework that generalizes certain aspects of word-representability, so that any binary language describes a graph class. In this work, we systematically study particularly small languages and observe that they characterize well-known graph classes, e.g., interval, permutation, circle, and bipartite chain graphs. Thus, we strengthen the bond between formal languages and graph classes, even for small binary languages. We also show some limitations of our approach by proving that, e.g., families of sparse graphs like planar graphs cannot be characterized by any language following this approach.

0.37

Pairwise Compatibility Graphs of Unweighted Caterpillars

cs.DM math.CO ·2026-10-10 ·Cyriac Antony, Manuel Lafond, Angelo Monti, Blerina Sinaimeri
similarity 0.65
Abstract

In this paper we study pairwise compatibility graphs whose witness tree is required to be an unweighted caterpillar. This is a natural restriction of PCGs, in the same line of research as the study of star witnesses, which led to the class of double-threshold graphs. In the caterpillar case, we show that this restriction is equivalent to a one-dimensional difference-labelling problem: a graph admits such a representation if and only if its vertices can be assigned integer labels so that adjacency is determined exactly by whether the absolute difference of two labels belongs to a given interval. Using this characterization, we derive structural properties of the class, including bounded twin-width, and study its relation with familiar graph families. We show that the class contains cycles and two-dimensional grids, while it excludes natural obstructions such as the subdivided star $S_{2,2,2,2,2}$, the cube graph $Q_3$, the wheel $W_6$, and the complement of the $3$-sunlet. We also consider restricted representations, including centipede witnesses and representations with a given interval and we give a polynomial-time recognition algorithm when the interval is fixed.

0.31

Flip-packability: uniform characterisations of tame graph classes

cs.LO cs.DMmath.COmath.LO ·2026-09-27 ·Ioannis Eleftheriadis
theory similarity 0.64
Abstract · 32 pages; added funding information

A class of graphs is monadically dependent if one cannot encode all graphs in coloured graphs from the class using a fixed first-order formula, and monadically stable if one cannot even encode arbitrarily long linear orders. Bonnet et al. (ICALP 2025) characterised monadic dependence by flip-separability: for every vertex weighting, boundedly many flips - complementations of the adjacency relation within a vertex subset - make every ball of radius $r$ carry at most an $\varepsilon$-fraction of the weight, so that every set carrying an $\varepsilon$-fraction has two elements pulled apart. We introduce flip-packability: boundedly many graphs, each obtained from the input by boundedly many flips and all determined by the weighting before any set is presented, such that every set carrying an $\varepsilon$-fraction of the weight has $m$ elements pairwise far apart in one of them. The number of flips producing each graph depends on the radius alone; only the number of graphs depends on $\varepsilon$ and $m$. We prove that a class of graphs is flip-packable if and only if it is monadically stable, and $2$-flip-packable, that is, flip-packable with $m=2$, if and only if it is monadically dependent. The passage from two scattered elements to $m$ is thus exactly what separates the two notions. For monadically stable classes we show that the flipped graphs can be computed from the weighting in cubic time. Varying the three parameters of the definition - the sparsifying operation, the radius, and the number $m$ of elements scattered - produces eight known characterisations of sparse and dense graph classes from the same template. In each case $m$ separates a depth-like notion from its width-like relaxation: treedepth from treewidth, shrubdepth from cliquewidth, and monadic stability from monadic dependence.

0.24

Non-induced inherent graphs

cs.DM math.CO ·2026-11-04 ·Vladimir Gurvich, Matjaž Krnc, Martin Milanič, Mikhail Vyalyi
similarity 0.63
Abstract

Concepts of avoidable paths and inherent two-rooted graphs were recently introduced for the case of induced subgraphs. In this paper, we translate this framework to the setting of not necessarily induced (NNI) subgraphs, where the structural constraints, as well as conclusions, are significantly relaxed. We develop a new sufficient condition for inherence, and use it to provide complete characterizations of inherent two-rooted paths and forks. We show that for these families, the obvious necessary condition for inherence from the induced case is sufficient in the NNI setting. To complement these results, we introduce two general methods for proving non-inherence and apply them to demonstrate the non-inherence of several classes of two-rooted trees. Keywords: subgraph, two-rooted graph, two-rooted tree, avoidable two-rooted graph, inherent two-rooted graph

0.25

Robust Algebraic Theories of Triangle Graphs

cs.FL ·2026-08-11 ·Marius Bozga, Radu Iosif, Florian Zuleger
theory similarity 0.63
Abstract

Triangle graphs are graphs of tree-width at most three in which every edge belongs to a triangle. This class encompasses well-known graph families such as Apollonian networks. We also consider fan graphs, a subclass of triangle graphs closely related to the 3-connected triangle graphs. Our main result is an algebraic characterization of both classes. We introduce two graph algebras based on parallel composition and a ternary serial composition, and show that they generate exactly the triangle and fan graphs, respectively. These algebras provide a natural extension of the classical algebra of series-parallel graphs from tree-width two to tree-width three. Building on these characterizations, we investigate context-free, recognizable, and logically-definable graph languages. We show that counting monadic second-order logic (CMSO) is decidable over the context-free sets of triangle and fan graphs. Moreover, we prove that recognizable graph languages coincide with languages definable in CMSO for both algebras.

0.04

Revisiting separators in string graphs, region intersection graphs, and induced-minor-free graphs

cs.CG math.COcs.DMmath.MG ·2026-10-16 ·James Davies, Paweł Rzążewski, Jack Spalding-Jamieson, Bartosz Walczak
top venuetheoryhighly cited similarity 0.61
Abstract · To appear at SODA 2027

String graphs are intersection graphs of continuous curves in the plane. In 2010, Fox and Pach proved that string graphs with $m$ edges admit balanced vertex separators of size $\mathcal{O}(m^{3/4}\sqrt{\log m})$ and conjectured that this bound can be improved to $\mathcal{O}(\sqrt{m})$, which would be optimal. After partial progress, Lee claimed in 2017 to prove this conjecture, and more generally to prove analogous separator theorems for region intersection graphs over minor-closed graph families. A key intermediate step in Lee's approach was a padded decomposition scheme for region intersection graphs. In 2024, Korhonen and Lokshtanov extended Lee's approach to the broader setting of graph classes excluding a fixed graph as an induced minor. These results have since found applications in a wide range of works. Later in 2024, a flaw was discovered in the construction of Lee's padded decomposition scheme, invalidating Lee's as well as Korhonen and Lokshtanov's separator results, and many works relying on them. In this work, we prove that string graphs with $m$ edges admit balanced separators of size $\mathcal{O}(\sqrt{m})$, and more generally obtain analogous $\mathcal{O}(\sqrt{m})$ bounds for region intersection graphs over fixed minor-closed graph families and for graphs excluding a fixed graph as an induced minor, thereby repairing the vast majority of the affected works. Furthermore, our balanced separators can be found in polynomial time. Our proof uses a different approach from Lee's and does not rely on padded decompositions. Since padded decompositions have also found applications independent of the separator theorems, particularly for string graphs, we also prove a padded decomposition result for region intersection graphs that is optimal for string graphs. We have formalized both the balanced separator and the padded decomposition results in Lean 4 with mathlib.

0.70

A Four-Connected Graph without a Legal System

cs.DM math.CO ·2026-09-11 ·Qiuyu Chen
theory similarity 0.60
Abstract

In a 2021 paper, Jankiewicz, Norin, and Wise asked whether there exists a finite $4$-connected graph of girth at least four and nonnegative Charney--Davis curvature such that no $4$-connected ordinary subgraph admits a legal system. We construct such a graph by starting from the hexagonal prism and attaching three $K_{3,4}$-based caps along pairwise disjoint induced $4$-cycles. The key structural input is a restriction theorem showing that a legal system on an induced-$4$-cycle amalgam restricts to each side, so the obstruction carried by the negatively curved prism survives the attachments. The resulting $33$-vertex graph is $4$-regular and $4$-connected, has girth four and Charney--Davis curvature one, and, by $4$-regularity, is its own unique $4$-connected ordinary subgraph.

0.42