We study the problem of reconfiguring a crossing-free embedding of a graph on a surface, with edges represented as curves, into another crossing-free embedding of the same graph on the same surface with the same fixed vertex positions. In this process, we reroute one edge at a time while maintaining crossing-free intermediate embeddings. This problem was introduced by Ito et al. [TALG 2025], who showed that even if the graph is a matching of two edges, reconfiguration is not always possible in the plane, but is always possible on the torus. For matchings of two or more edges, they gave a necessary and sufficient condition for reconfigurable embeddings in the plane, but not on the torus. Our main result is that for matchings, trees and forests, reconfiguration is always possible on the torus, and consequently, on any orientable surface of genus at least one. In addition, we provide sufficient conditions for reconfiguration on orientable surfaces of genus at least one and in the projective plane. For more general graphs, we show that reconfiguration is not always possible.

We consider facet-Hamiltonian cycles of polytopes, defined as cycles in their skeleton such that every facet is visited exactly once. These cycles can be understood as optimal watchman routes that guard the facets of a polytope. We consider the existence of such cycles for a variety of polytopes, the facets of which have a natural combinatorial interpretation. In particular, we prove the following results:

Abstract. Planar bipartite graphs can be represented as touching graphs of horizontal and vertical segments in [Formula: see text]. We study a generalization in space—touching graphs of axis-aligned rectangles in [Formula: see text]—and prove that planar 3-colorable graphs can be represented this way. The result implies a characterization of corner polytopes previously obtained by Eppstein and Mumford. A by-product of our proof is a distributive lattice structure on the set of orthogonal surfaces with given skeleton. Further, we study representations by axis-aligned non-coplanar rectangles in [Formula: see text] such that all regions are boxes. We show that the resulting graphs correspond to octahedrations of an octahedron. This generalizes the correspondence between planar quadrangulations and families of horizontal and vertical segments in [Formula: see text] with the property that all regions are rectangles.

A conjecture by Rafla from 1988 asserts that every simple drawing of the complete graph $K_n$ admits a plane Hamiltonian cycle. It turned out that already the existence of much simpler non-crossing substructures in such drawings is hard to prove. Recent progress was made by Aichholzer et al. and by Suk and Zeng who proved the existence of a plane path of length $Ω(\log n / \log \log n)$ and of a plane matching of size $Ω(n^{1/2})$ in every simple drawing of $K_n$. Instead of studying simpler substructures, we prove Rafla's conjecture for the subclass of convex drawings, the most general class in the convexity hierarchy introduced by Arroyo et al. Moreover, we show that every convex drawing of $K_n$ contains a plane Hamiltonian path between each pair of vertices (Hamiltonian connectivity) and a plane $k$-cycle for each $3 \leq k \leq n$ (pancyclicity), and present further results on maximal plane subdrawings.

Arrangements of pseudolines are classic objects in discrete and computational geometry. They have been studied with increasing intensity since their introduction almost 100 years ago. The study of the number $B_n$ of non-isomorphic simple arrangements of $n$ pseudolines goes back to Goodman and Pollack, Knuth, and others. It is known that $B_n$ is in the order of $2^{Θ(n^2)}$ and finding asymptotic bounds on $b_n = \frac{\log_2(B_n)}{n^2}$ remains a challenging task. In 2011, Felsner and Valtr showed that $0.1887 \leq b_n \le 0.6571$ for sufficiently large $n$. The upper bound remains untouched but in 2020 Dumitrescu and Mandal improved the lower bound constant to $0.2083$. Their approach utilizes the known values of $B_n$ for up to $n=12$. We tackle the lower bound by utilizing dynamic programming and the Lindström-Gessel-Viennot lemma. Our new bound is $b_n \geq 0.2721$ for sufficiently large $n$. The result is based on a delicate interplay of theoretical ideas and computer assistance.

Flip graphs of combinatorial and geometric objects are at the heart of many deep structural insights and connections between different branches of discrete mathematics and computer science. They also provide a natural framework for the study of reconfiguration problems. We study flip graphs of arrangements of pseudolines and of arrangements of pseudocircles, which are combinatorial generalizations of lines and circles, respectively. In both cases we consider triangle flips as local transformation and prove conjectures regarding their connectivity.

In 1926, Levi showed that, for every pseudoline arrangement $\mathcal{A}$ and two points in the plane, $\mathcal{A}$ can be extended by a pseudoline which contains the two prescribed points. Later extendability was studied for arrangements of pseudohyperplanes in higher dimensions. While the extendability of an arrangement of proper hyperplanes in $\mathbb{R}^d$ with a hyperplane containing $d$ prescribed points is trivial, Richter-Gebert found an arrangement of pseudoplanes in $\mathbb{R}^3$ which cannot be extended with a pseudoplane containing two particular prescribed points. In this article, we investigate the extendability of signotopes, which are a combinatorial structure encoding a rich subclass of pseudohyperplane arrangements. Our main result is that signotopes of odd rank are extendable in the sense that for two prescribed crossing points we can add an element containing them. Moreover, we conjecture that in all even ranks $r \geq 4$ there exist signotopes which are not extendable for two prescribed points. Our conjecture is supported by examples in ranks 4, 6, 8, 10, and 12 that were found with a SAT based approach.

A finite set $P$ of points in the plane is $n$-universal with respect to a class $\mathcal{C}$ of planar graphs if every $n$-vertex graph in $\mathcal{C}$ admits a crossing-free straight-line drawing with vertices at points of $P$. For the class of all planar graphs the best known upper bound on the size of a universal point set is quadratic and the best known lower bound is linear in $n$. Some classes of planar graphs are known to admit universal point sets of near linear size, however, there are no truly linear bounds for interesting classes beyond outerplanar graphs. In this paper, we show that there is a universal point set of size $2n-2$ for the class of bipartite planar graphs with $n$ vertices. The same point set is also universal for the class of $n$-vertex planar graphs of maximum degree $3$. The point set used for the results is what we call an exploding double chain, and we prove that this point set allows planar straight-line embeddings of many more planar graphs, namely of all subgraphs of planar graphs admitting a one-sided Hamiltonian cycle. The result for bipartite graphs also implies that every $n$-vertex plane graph has a $1$-bend drawing all whose bends and vertices are contained in a specific point set of size $4n-6$, this improves a bound of $6n-10$ for the same problem by Löffler and Tóth.

isomorphism classes of line arrangements).It can be decided in polynomial time whether an allowable sequence is realizable by an arrangement of approaching pseudo-lines. Furthermore, arrangements of approaching pseudo-lines can be transformed into each other by flipping triangular cells, i.e., they have a connected flip graph, and every bichromatic arrangement of this type contains a bichromatic triangular cell.

We study reconfiguration of independent sets in interval graphs under the token sliding rule. We show that if two independent sets of size k are reconfigurable in an n-vertex interval graph, then there is a reconfiguration sequence of length 𝒪(k⋅ n²). We also provide a construction in which the shortest reconfiguration sequence is of length Ω(k²⋅ n). As a counterpart to these results, we also establish that Independent Set Reconfiguration is PSPACE-hard on incomparability graphs, of which interval graphs are a special case.

Abstract A pseudocircle is a simple closed curve on the sphere or in the plane. The study of arrangements of pseudocircles was initiated by Grünbaum, who defined them as collections of simple closed curves that pairwise intersect in exactly two crossings. Grünbaum conjectured that the number of triangular cells $$p_3$$ p 3 in digon-free arrangements of n pairwise intersecting pseudocircles is at least $$2n-4$$ 2 n - 4 . We present examples to disprove this conjecture. With a recursive construction based on an example with 12 pseudocircles and 16 triangles we obtain a family of intersecting digon-free arrangements with $$p_3({\mathscr {A}})/n \rightarrow 16/11 = 1.\overline{45}$$ p 3 ( A ) / n → 16 / 11 = 1 . 45 ¯ . We expect that the lower bound $$p_3({\mathscr {A}}) \ge 4n/3$$ p 3 ( A ) ≥ 4 n / 3 is tight for infinitely many simple arrangements. It may however be true that all digon-free arrangements of n pairwise intersecting circles have at least $$2n-4$$ 2 n - 4 triangles. For pairwise intersecting arrangements with digons we have a lower bound of $$p_3 \ge 2n/3$$ p 3 ≥ 2 n / 3 , and conjecture that $$p_3 \ge n-1$$ p 3 ≥ n - 1 . Concerning the maximum number of triangles in pairwise intersecting arrangements of pseudocircles, we show that $$p_3 \le \frac{4}{3}\left( {\begin{array}{c}n\\ 2\end{array}}\right) +O(n)$$ p 3 ≤ 4 3 n 2 + O ( n ) . This is essentially best possible because there are families of pairwise intersecting arrangements of n pseudocircles with $$p_3 = \frac{4}{3}\left( {\begin{array}{c}n\\ 2\end{array}}\right) $$ p 3 = 4 3 n 2 . The paper contains many drawings of arrangements of pseudocircles and a good fraction of these drawings was produced automatically from the combinatorial data produced by our generation algorithm. In the final section we describe some aspects of the drawing algorithm.

We study covering numbers and local covering numbers with respect to difference graphs and complete bipartite graphs. In particular, we show that in every cover of a Young diagram with $\binom{2k}{k}$ steps with generalized rectangles, there is a row or a column in the diagram that is used by at least $k+1$ rectangles and prove that this is best possible. This answers two questions by Kim et al. [ European J. Combin., 86 (2020), 103074], namely, what is the local complete bipartite covering number of a difference graph, and is there a sequence of graphs with a constant local difference graph covering numbers and unbounded local complete bipartite covering numbers? We add to the study of these local covering numbers with a lower bound construction and some examples. Following Kim et al., we use the results on local covering numbers to provide lower and upper bounds for the local dimension of partially ordered sets of height 2. We discuss the local dimension of some posets related to Boolean lattices and show that the poset induced by the first two layers of the Boolean lattice has local dimension $(1 + o(1))\log_2\log_2 n$. We conclude with some remarks on covering numbers for digraphs and Ferrers dimension.

A vertex coloring φ of a graph G is p-centered if for every connected subgraph H of G either φ uses more than p colors on H or there is a color that appears exactly once on H Centered colorings form one of the families of parameters that allow to capture notions of sparsity of graphs: A class of graphs has bounded expansion if and only if there is a function f such that for every p ≥ 1, every graph in the class admits a p-centered coloring using at most f(p) colors. In this paper, we give upper bounds for the maximum number of colors needed in a p-centered coloring of graphs from several widely studied graph classes. We show that: (1) planar graphs admit p-centered colorings with (p3 log p) colors where the previous bound was (p19); (2) bounded degree graphs admit p-centered colorings with (p) colors while it was conjectured that they may require exponential number of colors in p; (3) graphs avoiding a fixed graph as a topological minor admit p-centered colorings with a polynomial in p number of colors. All these upper bounds imply polynomial algorithms for computing the colorings. Prior to this work there were no non-trivial lower bounds known. We show that: (4) there are graphs of treewidth t that require colors in any p-centered coloring and this bound matches the upper bound; (5) there are planar graphs that require Ω(p2 log p) colors in any p-centered coloring. We also give asymptotically tight bounds for outerplanar graphs and planar graphs of treewidth 3. We prove our results with various proof techniques. The upper bound for planar graphs involves an application of a recent structure theorem while the upper bound for bounded degree graphs comes from the entropy compression method. We lift the result for bounded degree graphs to graphs avoiding a fixed topological minor using the Grohe-Marx structure theorem.

The flip graph of triangulations has as vertices all triangulations of a convex $n$-gon and an edge between any two triangulations that differ in exactly one edge. An $r$-rainbow cycle in this graph is a cycle in which every inner edge of the triangulation appears exactly $r$ times. This notion of a rainbow cycle extends in a natural way to other flip graphs. In this paper we investigate the existence of $r$-rainbow cycles for three different flip graphs on classes of geometric objects: the aforementioned flip graph of triangulations of a convex $n$-gon, the flip graph of plane trees on an arbitrary set of $n$ points, and the flip graph of noncrossing perfect matchings on a set of $n$ points in convex position. In addition, we consider two flip graphs on classes of nongeometric objects: the flip graph of permutations of $\{1,2,\dots,n\}$ and the flip graph of $k$-element subsets of $\{1,2,\dots,n\}$. In each of the five settings, we prove the existence and nonexistence of rainbow cycles for different values of $r$, $n$, and $k$.

The dimension of a partial order $P$ is the minimum number of linear orders whose intersection is $P$. There are efficient algorithms to test if a partial order has dimension at most 2. In 1982 Yannakakis [SIAM J. Algebraic Discrete Methods, 3 (1982), pp. 351--358] showed that for $k\geq 3$ to test if a partial order has dimension $\leq k$ is NP-complete. The height of a partial order $P$ is the maximum size of a chain in $P$. Yannakakis also showed that for $k\geq 4$ to test if a partial order of height $2$ has dimension $\leq k$ is NP-complete. The complexity of deciding whether an order of height 2 has dimension 3 was left open. This question became one of the best known open problems in dimension theory for partial orders. We show that the problem is NP-complete. Technically, we show that the decision problem (3DH2) for dimension is equivalent to deciding for the existence of bipartite triangle containment representations (BTCon). This problem then allows a reduction from a class of planar satisfiability problems (P-3-CON-3-SAT(4)) which is known to be NP-hard.

A straight-line drawing of a graph is a monotone drawing if for each pair of vertices there is a path which is monotonically increasing in some direction, and it is called a strongly monotone drawing if the direction of monotonicity is given by the direction of the line segment connecting the two vertices. We present algorithms to compute crossing-free strongly monotone drawings for some classes of planar graphs; namely, 3-connected planar graphs, outerplanar graphs, and 2-trees. The drawings of 3-connected planar graphs are based on primal-dual circle packings. Our drawings of outerplanar graphs depend on a new algorithm that constructs strongly monotone drawings of trees which are also convex. For irreducible trees, these drawings are strictly convex.

We study on-line colorings of certain graphs given as intersection graphs of objects "between two lines", i.e., there is a pair of horizontal lines such that each object of the representation is a connected set contained in the strip between the lines and touches both. Some of the graph classes admitting such a representation are permutation graphs (segments), interval graphs (axis-aligned rectangles), trapezoid graphs (trapezoids) and cocomparability graphs (simple curves). We present an on-line algorithm coloring graphs given by convex sets between two lines that uses O(w^3) colors on graphs with maximum clique size w. In contrast intersection graphs of segments attached to a single line may force any on-line coloring algorithm to use an arbitrary number of colors even when w=2. The left-of relation makes the complement of intersection graphs of objects between two lines into a poset. As an aside we discuss the relation of the class C of posets obtained from convex sets between two lines with some other classes of posets: all 2-dimensional posets and all posets of height 2 are in C but there is a 3-dimensional poset of height 3 that does not belong to C. We also show that the on-line coloring problem for curves between two lines is as hard as the on-line chain partition problem for arbitrary posets.

Schnyder characterized planar graphs in terms of order dimension. The structures used for the proof have found many applications. Researchers also found several extensions of the seminal result. A particularly far-reaching extension is the Brightwell--Trotter theorem about planar maps. It states that the order dimension of the incidence poset $\mathbf{P}_{\mathbf{M}}$ of vertices, edges, and faces of a planar map $\mathbf{M}$ has dimension at most 4. The original proof generalizes the machinery of Schnyder paths and Schnyder regions. In this short paper we use a simple result about the order dimension of grid intersection graphs to show a slightly stronger result: $\dim(\mathsf{split}(\mathbf{P}_{\mathbf{M}})) \leq 4$. Here, $\mathsf{split}(P)$ refers to a particular order of height two associated with $P$. The Brightwell--Trotter theorem follows because $\dim(\mathsf{split}(P)) \geq \dim(P)$ holds for every $P$. This may be the first result in the area that is obtained without using the tools introduced by Schnyder.

In a rectilinear dual of a planar graph vertices are represented by simple rectilinear polygons, while edges are represented by side-contact between the corresponding polygons. A rectilinear dual is called a cartogram if the area of each region is equal to a pre-specified weight.

We prove that every planar graph has a representation using axis-parallel cubes in three dimensions in such a way that there is a cube corresponding to each vertex of the planar graph and two cubes have a non-empty intersection if and only if their corresponding vertices are adjacent. Moreover, when two cubes have a non-empty intersection, they just touch each other. This result is a strengthening of a result by Thomassen which states that every planar graph has such a representation using axis-parallel boxes.

The linear extension diameter of a finite poset $\mathcal{P}$ is the maximum distance between a pair of linear extensions of $\mathcal{P}$, where the distance between two linear extensions is the number of pairs of elements of $\mathcal{P}$ appearing in different orders in the two linear extensions. We prove a formula for the linear extension diameter of the Boolean lattice and characterize the diametral pairs of linear extensions. For the more general case of a downset lattice $\mathcal{D}_{\mathcal{P}}$ of a 2-dimensional poset $\mathcal{P}$, we characterize the diametral pairs of linear extensions of $\mathcal{D}_{\mathcal{P}}$ and show how to compute the linear extension diameter of $\mathcal{D}_{\mathcal{P}}$ in time polynomial in $|\mathcal{P}|$.

Given a set P of points in the plane we are interested in points that are 'deep' in the set in the sense that they have two opposite quadrants both containing many points of P. We deal with the extremal version of this problem. A pair (a, b) of numbers is admissible if every point set P contains a point p ∈ P that determines a pair (Q,Qop) of opposite quadrants, such that Q contains at least an a-fraction and Qop contains at least a b-fraction of the points of P. We provide a complete description of the set F of all admissible pairs (a, b). This amounts to identifying three line segments and a point on the boundary of F.

The distance between two permutations of the same set X is the number of pairs of elements that are in different order in the two permutations. Given a poset $P=(X,\leq)$, a pair $L_1,L_2$ of linear extensions is called a diametral pair if it maximizes the distance among all pairs of linear extensions of P. The maximal distance is called the linear extension diameter of P and is denoted led(P). Alternatively led(P) is the maximum number of incomparable pairs of a two-dimensional extension of P. In the first part of the paper we discuss upper and lower bounds for led(P). These bounds relate led(P) to well-studied parameters like dimension and height. We prove that led(P) is a comparability invariant and determine the linear extension diameter for the class of generalized crowns. For the Boolean lattices we have partial results. A diametral pair generates a minimal two-dimensional extension of P or, equivalently, a maximal interval in the graph of linear extensions of P. Studies of such intervals lead to the definition of new classes of linear extensions. We give three characterizations of the class of extremal linear extensions which contains the greedy linear extensions. With complementary linear extensions we introduce a class contained in the set of super-greedy linear extensions. The complementary linear extension of L is the linear extension L* obtained by taking the reverse of L as a priority list in the generic algorithm for linear extensions. A complementary pair is a pair L,M of linear extensions with M=L* and L=M*. Iterations of the complementary mapping starting from an arbitrary linear extension eventually lead to a complementary pair.

Article Point-sets with few k-sets Share on Authors: Helmut Alt Institut für Informatik, Freie Universität Berlin, Takustr. 9, 14195 Berlin, Germany Institut für Informatik, Freie Universität Berlin, Takustr. 9, 14195 Berlin, GermanyView Profile , Stefan Felsner Institut für Informatik, Freie Universität Berlin, Takustr. 9 14195 Berlin, Germany Institut für Informatik, Freie Universität Berlin, Takustr. 9 14195 Berlin, GermanyView Profile , Ferran Hurtado Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Pau Gargallo 5, 08028-Barcelona, España Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Pau Gargallo 5, 08028-Barcelona, EspañaView Profile , Marc Noy Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Pau Gargallo 5, 08028-Barcelona, España Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Pau Gargallo 5, 08028-Barcelona, EspañaView Profile Authors Info & Claims SCG '98: Proceedings of the fourteenth annual symposium on Computational geometryJune 1998 Pages 200–205https://doi.org/10.1145/276884.276907Published:07 June 1998 0citation149DownloadsMetricsTotal Citations0Total Downloads149Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A chain of a set P of n points in the plane is a chain of the dominance order on P. A k-chain is a subset C of P that can be covered by k chains. A k-chain C is a maximum k-chain if no other k-chain contains more elements than C. This paper deals with the problem of finding a maximum k-chain of P in the cardinality and in the weighted case. Using the skeleton S(P) of a point set P introduced by Viennot we describe a fairly simple algorithm that computes maximum k-chains in time O(kn log n) and linear space. The basic idea is that the canonical chain partition of a maximum (k-1)-chain in the skeleton S(P) provides k regions in the plane such that a maximum k-chain for P can be obtained as the union of a maximal chain from each of these regions. By the symmetry between chains and antichains in the dominance order we may use the algorithm for maximum k-chains to compute maximum k-antichains for planar points in time O(kn log n). However, for large k one can do better. We describe an algorithm computing maximum k-antichains (and, by symmetry, k-chains) in time O((n 2 k) log n) and linear space. Consequently, a maximum k-chain can be computed in time O(n 3/2 log n) for arbitrary k. The background for the algorithms is a geometric approach to the Greene--Kleitman theory for permutations. We include a skeleton-based exposition of this theory and give some hints on connections with the theory of Young tableaux. The concept of the skeleton of a planar point set is extended to the case of a weighted point set. This extension allows to compute maximum weighted k-chains with an algorithm that is similar to the algorithm for the cardinality case. The time and space requirements of the algorithm for weighted k-chains are O(2 kn log(2 kn )) and O(2 kn ), respectively.

Given a simple arrangement of n pseudolines in the Euclidean plane, associate with line i the list σi of the lines crossing i in the order of the crossings on line i. \(\sigma_i=(\sigma^i_1,\sigma^i_2,\ldots,\sigma^i_{n-1})\) is a permutation of \(\{1,\ldots,n\} - \{i\}\) . The vector (σ1 ,σ2, ...,σ_n) is an encoding for the arrangement. Define \(\tau^i_j = 1\) if \(\sigma^i_j > i\) and \(\tau^i_j = 0\) , otherwise. Let \(\tau_i=(\tau^i_1,\tau^i_2,\ldots,\tau^i_{n-1})\) , we show that the vector (τ1, τ2, ... , τ_n) is already an encoding.

This paper investigates a transformation $P \to Q$ between partial orders $P,Q$ that transforms the interval dimension of P to the dimension of Q, i.e., $\text{idim} ( P ) = \dim ( Q )$. Such a construction has been shown before in the context of Ferrer’s dimension by Cogis [Discrete Math., 38 (1982), pp. 47–52]. The construction in this paper can be shown to be equivalent to his, but it has the advantage of (1) being purely order-theoretic, (2) providing a geometric interpretation of interval dimension similar to that of Ore [Amer. Math. Soc. Colloq. Publ., Vol. 38, 1962] for dimension, and (3) revealing several somewhat surprising connections to other order-theoretic results. For instance, the transformation $P \to Q$ can be seen as almost an inverse of the well-known split operation; it provides a theoretical background for the influence of edge subdivision on dimension (e.g., the results of Spinrad [Order, 5 (1989), pp. 143–147]) and interval dimension, and it turns out to be invariant with respect to changes of P that do not alter its comparability graph, thus also providing a simple new proof for the comparability invariance of interval dimension.

Article Free Access Share on Maximum k-chains in planar point sets: combinatorial structure and algorithms Authors: Stefan Felsner View Profile , Lorenz Wernisch View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 146–153https://doi.org/10.1145/167088.167136Online:01 June 1993Publication History 1citation210DownloadsMetricsTotal Citations1Total Downloads210Last 12 Months9Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF