CS Paper Radar

$k$-arrangements of pseudolines and pseudocircles

Jan Kynčl, Carolina Medina, Gelasio Salazar

cs.CG math.CO ·submitted 2026-09-30 22:09 UTC · v1
theory

Abstract

A $k$-arrangement of pseudolines is a set of bi-infinite curves in the plane such that any two of them intersect each other in exactly $k$ points, at which they cross, and it is simple if no three curves meet at a common point. Cyclic arrangements are the only simple $1$-arrangements of pseudolines that are unavoidable, in the Ramsey spirit: for each fixed $m\ge 1$, every sufficiently large simple $1$-arrangement of pseudolines has a cyclic subarrangement of size $m$. We show that, for every $m\ge 3$, the number of unavoidable simple $k$-arrangements of pseudolines of size $m$ grows exponentially with $k$, independently of $m$. For even $k$, we prove an analogous result for $k$-arrangements of pseudocircles.

Comment
19 pages, 10 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Non-simple Arrangements of Lines and Pseudolines with Many Triangles

cs.CG math.CO ·2026-11-02 ·Roman Parpalak, Denis Utkin
code/data similarity 0.69
Abstract · 72 pages, 19 figures, 8 tables. Code, enumeration outputs and certificates: https://github.com/parpalak/nonsimple-arrangements

We study affine arrangements of an even number $n$ of lines and pseudolines with many triangles. For simple ones, Blanc's bound limits the number of triangular faces to $\lfloor n(n-5/2)/3\rfloor$. Adapting the Bartholdi-Blanc-Loisel doubling to the even case, we construct an infinite series of arrangements of $n=6\cdot2^t+2$ ($8,14,26,50,\ldots$) straight lines with two triple points and $(n(n-5/2)+1)/3$ triangles, one more than the simple bound allows. We obtain exhaustive enumerations of triangle-maximal pseudoline arrangements, simple or not, for even $n\le12$. For $n=6,8,10,12,14$ the maximum number of triangles, for both lines and pseudolines, is $7,15,25,38,54$; for $n=8,12,14$ every optimal arrangement has multiple points. All optimal arrangements for even $n\le12$ are realizable by straight lines, except two arrangements of 10 pseudolines, which are not stretchable. For the odd value $n=11$, no arrangement with $33$ triangles exists even with multiple points. We also obtain even arrangements by adding a line to odd ones. For $n\equiv2\pmod 6$ this again gives one triangle more than the simple bound, in pseudolines up to $n=44$ and in straight lines for $n=20$ and $n=32$. Doubling these pseudoline arrangements gives members of the series $18\cdot2^t+2$ and $30\cdot2^t+2$ with the same excess, up to $n=146$ and $n=242$, respectively; those with $n=38$ and $n=74$ are realizable by straight lines. These results lead us to conjecture that an arrangement of an even number $n$ of pseudolines has at most $\lfloor n(n-2)/3\rfloor-\lfloor n/6\rfloor$ triangles.

0.34

Every $k$-Quasi-Planar Graph Has Linearly Many Edges

cs.CG math.CO ·2026-11-01 ·Ankan Sadhu
theory similarity 0.63
Abstract · 6 pages, 1 figure

For every fixed integer $k\ge2$, we prove that every simple graph on $n$ vertices drawn in the plane with no $k$ pairwise crossing edges has at most $C_kn$ edges, where $C_k$ depends only on $k$. We allow any finite number of proper crossings between two edges, including edges with a common endpoint. For $n\ge3$, removing a small disk around each vertex turns the drawing into a family of arcs on a sphere with $n$ boundary circles. Each arc joins two different boundary circles, and different edges have different unordered pairs of endpoint circles. The arcs are therefore essential and pairwise nonhomotopic, with endpoints allowed to move along their boundary circles during a homotopy. Any family of pairwise intersecting lifts to the universal cover projects to distinct graph edges that cross pairwise. Its size is consequently at most $k-1$. Beeker and Lazarovich's theorem on surface patterns then bounds the number of arcs. Their estimate is linear in the size of a triangulation, and an explicit triangulation of the $n$-holed sphere has linearly many edges and triangles.

0.54

Some results on Archdeacon's conjecture for rotation systems

cs.CG math.CO ·2026-09-10 ·Arahat Chikkatur, Ji Zeng
theory similarity 0.60
Abstract

A rotation system on $n$ elements assigns to each element a cyclic order of the other $n-1$ elements. A four-element subset is non-planar if its induced rotation system cannot be realized by a crossing-free drawing of $K_4$. As a combinatorial strengthening of Hill's conjecture on the crossing number of the complete graph, Archdeacon conjectured that every rotation system on $n$ elements has at least $H(n)=\frac{1}{4} \lfloor\frac {n}{2}\rfloor \lfloor\frac{n-1}{2}\rfloor \lfloor\frac{n-2}{2}\rfloor \lfloor\frac{n-3}{2}\rfloor$ non-planar four-element subsets. We computationally verify Archdeacon's conjecture for $n\leq 10$ and show that every extremal rotation system in these orders is realizable by a simple drawing. With computer assistance, we prove that every rotation system on $n$ elements has at least $(8/9 - o(1)) H(n)$ non-planar four-element subsets. We also present a proof by hand for a weaker lower bound of $(2/3-o(1)) H(n)$. Finally, extending recent work of Felsner on antipodal pairs in drawings, we show that Archdeacon's conjecture holds for antipodally shellable rotation systems.

0.39

A linear bound for nested cycles without geometric crossings

cs.DM math.CO ·2026-09-02 ·Jiangdong Ai, Gregory Gutin, Yiming Hao
theoryhot direction similarity 0.60
Abstract

Cycles $C_1,\ldots,C_k$ in a graph are called nested without geometric crossings if they are pairwise edge-disjoint, $V(C_k)\subseteq\cdots\subseteq V(C_1)$, and each pair of consecutive cycles induces the same cyclic order on the vertices of the inner cycle, up to reversal. Let $f_k(n)$ be the least number of edges that forces such a family in every $n$-vertex graph. Gil Fernández, Kim, Kim and Liu proved that $f_2(n)=O(n)$, answering a question of Erdős, and asked whether $f_k(n)=O_k(n)$ for every fixed $k$. We prove this for all $k$. The proof selects the inner cycles together with a disjoint subgraph that supplies their external neighbours. A reselection argument gives disjoint paths from every inner-cycle vertex to any sufficiently large target set. Sublinear expansion and a rooted clique minor then allow the vertices to be joined in the required cyclic order.

0.25

Larger Crossing Families

cs.CG math.CO ·2026-10-28 ·Joachim Orthaber, Patrick Schnider
similarity 0.58
Abstract

We give the first explicit constant for crossing families of linear size by showing that every set of $n$ points in general position in the plane contains a crossing family of size approximately $\frac{n}{79}$. We further identify some conditions where there are even larger crossing families. The first such condition forbids the existence of a large different pattern, namely non-convex 4-clusters: We show that every point set contains either a large non-convex 4-cluster or a large crossing family. The second condition is the existence of many crossings: We give a bound for the size of a crossing family in terms of the number of crossings of the complete geometric graph drawn on the point set.

0.23

Almost Linear Universal Point Sets for Planar Graphs

cs.CG math.CO ·2026-09-10 ·Taylor Gordon
theorycode/data similarity 0.58
Abstract · 12 pages, 2 figures. Lean formalization of the earlier construction: https://github.com/taylorgordon20/math/tree/main/213-superpatterns

A point set is universal for planar graphs on $n$ vertices if every such graph has a straight-line drawing without crossings whose vertices belong to the set. We construct universal point sets of size $n^{1+o(1)}$, improving the previous quadratic upper bound. Our construction uses the reduction of Bannister, Cheng, Devanny, and Eppstein from universal point sets to superpatterns for $213$-avoiding permutations. We represent these permutations by ordered rooted forests and construct a small family of intervals containing every such forest. The result follows from a straightforward bound on the size of the family of intervals. GPT-6 Astra assisted in developing the construction and proof.

0.37

Minimum central circles: an effective characterization of the global asymptotic constant

cs.CG math.MG ·2026-09-12 ·Maurizio Falconi
theoryhot direction similarity 0.57
Abstract · 9 pages. Revised exposition and reproducibility documentation. Standalone proof supplements S1 and S2 are supplied as ancillary PDFs, with t…

Let $R^\ast(n)$ be the minimum radius of a central circle externally tangent to nonoverlapping circles of radii $1,\ldots,n$. We prove that $R^\ast(n)=C_\ast n^2+o(n^2)$ and give finite linear programs that enclose $C_\ast$ with prescribed error. An exact angular comparison reduces the problem to marked points on a line with separation at least the geometric mean of each pair of marks. Concatenation with bounded joining cost and reassignment to the prescribed normalized radii prove existence of the limit. Balanced finite-word programs give a bracket of width $(1/k+1/r)/π$, before directed arithmetic error, using $k$ types and words of length $r$. We also obtain explicit geometric bounds. For the upper bound, we recover finite and countable reflected-block constructions by actual permutations, retaining all pair constraints. A coupled terminal-subset argument gives an explicit lower bound strictly above $1/8$. Together these give $C_{\rm term}+η_{\rm width}\le C_\ast\le U_4$. The lower endpoint comes from the terminal-subset argument, and the upper endpoint from the four-block construction; neither is asserted sharp. The finite-word scheme establishes computability; efficient high-precision evaluation and the structure of global optimizers remain open.

0.29

Computing distances in braid-move graphs, higher Bruhat orders, and oriented-matroid mutation graphs is NP-hard

cs.DM math.CO ·2026-10-01 ·Tilen Marc
theorycode/data similarity 0.56
Abstract · 33 pages, 5 figures. v2: restructured and several proofs shortened. Code, computational checks and Lean formalization: https://github.com/ti…

A wiring diagram is an arrangement of $m$ pseudolines, every two of which cross exactly once. Reading its crossings from left to right encodes it as a reduced word of the permutation $w_0\in S_m$ that reverses $1,\dots,m$, unique up to commutations, and a braid move $σ_iσ_{i+1}σ_i\leftrightarrowσ_{i+1}σ_iσ_{i+1}$ flips one of its triangles. We prove that deciding whether two wiring diagrams are within a given braid-move distance is NP-complete. Equivalently, deciding flip distance is NP-complete in the higher Bruhat order $B(m,2)$, for triangle flips of marked arrangements of pseudolines, and for rhombic tilings of a $2m$-gon; this answers an open question on flip graphs of pseudoline arrangements (SODA 2024). The reduction is from Vertex Cover: for every graph $G$ we construct two wiring diagrams at braid-move distance $|D|+2\operatorname{VC}(G)$, where $\operatorname{VC}(G)$ is the vertex cover number of $G$ and the Hamming distance $|D|$ is the number of triples of wires whose triangles are oriented differently. The construction glues copies of a seven-wire gadget whose braid-move distance exceeds its Hamming distance by $2$. Adding a line at infinity transfers the construction to rank-$3$ uniform oriented matroids, where two oriented matroids are adjacent in the mutation graph if their chirotopes differ in one basis; so deciding distance in the mutation graph is NP-complete in rank $3$. An iterate of Rambau's expansion of signotopes amplifies the excess and gives NP-hardness in every fixed rank $r\ge4$, and by duality in every fixed corank at least $3$. The same instances show that flip distance in the higher Bruhat orders $B(n,k)$ is NP-complete for every fixed $k\ge2$.

0.46