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.

Abstract Given a set of n labeled points in general position in the plane, we remove all of its points one by one. At each step, one point from the convex hull of the remaining set is erased. In how many ways can the process be carried out? The answer obviously depends on the point set. If the points are in convex position, there are exactly n! ways, which is the maximum number of ways for n points. But what is the minimum number? It is shown that this number is (roughly) at least $$3^n$$ 3 n and at most $$12.29^n$$ 12 . 29 n .

Abstract We prove that for any $$\ell _p$$ ℓ p -norm in the plane with $$1< p< \infty $$ 1 < p < ∞ and for every infinite $$\mathcal {M}\subset \mathbb {R}^2$$ M ⊂ R 2 , there exists a two-colouring of the plane such that no isometric copy of $$\mathcal {M}$$ M is monochromatic. On the contrary, we show that for every polygonal norm (that is, the unit ball is a polygon) in the plane, there exists an infinite $$\mathcal {M}\subset \mathbb {R}^2$$ M ⊂ R 2 such that for every two-colouring of the plane there exists a monochromatic isometric copy of $$\mathcal {M}$$ M .

Abstract. We consider partitions of a point set into two parts, and the lengths of the minimum spanning trees (MSTs) of the original set and of the two parts. If [Formula: see text] denotes the length of an MST of [Formula: see text], we show that every set [Formula: see text] of [Formula: see text] points admits a nontrivial bipartition [Formula: see text] for which the MST-ratio [Formula: see text] is strictly larger than 1 and that 1 is the largest number with this property. Furthermore, we provide a fast algorithm that computes such a bipartition in [Formula: see text] time and one that computes the corresponding MST-ratio in [Formula: see text] time. In certain settings, a much better MST-ratio can be guaranteed. For example, if [Formula: see text] is a set of [Formula: see text] random points uniformly distributed in [Formula: see text], then for any [Formula: see text], the MST-ratio in a maximizing partition is at least [Formula: see text] with probability tending to 1 as [Formula: see text]. Our results and techniques are extendable to higher dimensions.

A matchstick graph is a plane graph with edges drawn as unit distance line segments. This class of graphs was introduced by Harborth who conjectured that a matchstick graph on n vertices can have at most ⌊3n-√{12n-3}⌋ edges. Recently his conjecture was settled by Lavollée and Swanepoel. In this paper we consider 1-planar unit distance graphs. We say that a graph is a 1-planar unit distance graph if it can be drawn in the plane such that all edges are drawn as unit distance line segments while each of them are involved in at most one crossing. We show that such graphs on n vertices can have at most 3n-∜{n}/10 edges.

A graph is 1-planar, if it can be drawn in the plane such that there is at most one crossing on every edge. It is known, that 1-planar graphs have at most 4n−8 edges. We prove the following odd-even generalization. If a graph can be drawn in the plane such that every edge is crossed by at most one other edge an odd number of times, then it is called 1-odd-planar and it has at most 5n−9 edges. As a consequence, we improve the constant in the Crossing Lemma for the odd-crossing number, if adjacent edges cross an even number of times. We also give upper bound for the number of edges of k-odd-planar graphs.

The disjointness graph of a set system is a graph whose vertices are the sets, two being connected by an edge if and only if they are disjoint. It is known that the disjointness graph G of any system of segments in the plane is χ-bounded, that is, its chromatic number χ(G) is upper bounded by a function of its clique number ω(G). Here we show that this statement does not remain true for systems of polygonal chains of length 2. We also construct systems of polygonal chains of length 3 such that their disjointness graphs have arbitrarily large girth and chromatic number. In the opposite direction, we show that the class of disjointness graphs of (possibly self-intersecting) 2-way infinite polygonal chains of length 3 is χ-bounded: for every such graph G, we have χ(G) ≤ (ω(G))³+ω(G).

Abstract The crossing number of a graph G is the minimum number of edge crossings over all drawings of G in the plane. A graph G is k-crossing-critical if its crossing number is at least k, but if we remove any edge of G, its crossing number drops below k. There are examples of k-crossing-critical graphs that do not have drawings with exactly k crossings. Richter and Thomassen proved in 1993 that if G is k-crossing-critical, then its crossing number is at most $$2.5\, k+16$$ 2.5 k + 16 . We improve this bound to $$2k+8\sqrt{k}+47$$ 2 k + 8 k + 47 .

Abstract A planar point set of n points is called $$\gamma $$ γ -dense if the ratio of the largest and smallest distances among the points is at most $$\gamma \sqrt{n}$$ γ n . We construct a dense set of n points in the plane with $$ne^{\Omega ({\sqrt{\log n}})}$$ n e Ω ( log n ) halving lines. This improves the bound $$\Omega (n\log n)$$ Ω ( n log n ) of Edelsbrunner et al. (Discrete Comput Geom 17(3):243–255, 1997). Our construction can be generalized to higher dimensions, for any d we construct a dense point set of n points in $$\mathbb {R}^d$$ R d with $$n^{d-1}e^{\Omega ({\sqrt{\log n}})}$$ n d - 1 e Ω ( log n ) halving hyperplanes. Our lower bounds are asymptotically the same as the best known lower bounds for general point sets.

Let G be a drawing of a graph with n vertices and $$e>4n$$ edges, in which no two adjacent edges cross and any pair of independent edges cross at most once. According to the celebrated Crossing Lemma of Ajtai, Chvátal, Newborn, Szemerédi and Leighton, the number of crossings in G is at least $$c\,{e^3\over n^2}$$ , for a suitable constant $$c>0$$ . In a seminal paper, Székely generalized this result to multigraphs, establishing the lower bound $$c\,{e^3\over mn^2}$$ , where m denotes the maximum multiplicity of an edge in G. We get rid of the dependence on m by showing that, as in the original Crossing Lemma, the number of crossings is at least $$c'{e^3\over n^2}$$ for some $$c'>0$$ , provided that the “lens” enclosed by every pair of parallel edges in G contains at least one vertex. This settles a conjecture of Bekos, Kaufmann, and Raftopoulou.

The disjointness graph G=G(S) of a set of segments S in R^d, d>1 is a graph whose vertex set is S and two vertices are connected by an edge if and only if the corresponding segments are disjoint. We prove that the chromatic number of G satisfies chi(G)<=omega(G)^4+omega(G)^3 where omega(G) denotes the clique number of G. It follows, that S has at least cn^{1/5} pairwise intersecting or pairwise disjoint elements. Stronger bounds are established for lines in space, instead of segments. We show that computing omega(G) and chi(G) for disjointness graphs of lines in space are NP-hard tasks. However, we can design efficient algorithms to compute proper colorings of G in which the number of colors satisfies the above upper bounds. One cannot expect similar results for sets of continuous arcs, instead of segments, even in the plane. We construct families of arcs whose disjointness graphs are triangle-free (omega(G)=2), but whose chromatic numbers are arbitrarily large.

Suppose that the whole plane (or a large region) is monitored by aset S of stationary sensors such that each element s ∈ S canobserve an axis-parallel unit square R(s) centered at s, whichis called the range of s. Each sensor s is equipped witha battery of unit lifetime. Is it true that if every point of theplane belongs to the range of many sensors, then we can monitorthe plane for a long time without running out of power? If S canbe partitioned into k parts S1, S2,..., Sk such that, foreach i, the sensors in Si together can observe the wholeplane, then the plane can be monitored with no interruption fork units of time. Indeed, we can first switch on all sensorsbelonging to S1. After these sensors run out of battery, we canswitch on all elements of S2, etc.We arrive at the following problem. Let m(k) denote the smallestpositive integer m such that any m-fold covering of the planewith axis-parallel unit squares splits into at least kcoverings. We show that m(k)=O(k2), and generalize this resultto translates of any centrally symmetric convex polygon in theplace of squares. From the other direction, we know only that m(k) ≥ ⌊4k/3⌋ -1.

Let G be a graph without loops or multiple edges drawn in the plane. It is shown that, for any k, if G has at least $C_k n$ edges and n vertices, then it contains three sets of k edges, such that every edge in any of the sets crosses all edges in the other two sets. Furthermore, two of the three sets can be chosen such that all k edges in the set have a common vertex.

Let G be a graph with n vertices and e ≥ 4n edges, drawn in the plane in such a way that if two or more edges (arcs) share an interior point p ,then they must properly cross one another at p. It is shown that the number of crossing points, counted without multiplicity, is at least constant times e and that the order of magnitude of this bound cannot be improved. If, in addition, two edges are allowed to cross only at most once, then the number of crossing points must exceed constant times (e/n)4.

Twenty years ago, Ajtai, Chvatal, Newborn, Szemeredi, and, independently, Leighton discovered that the crossing number of any graph with v vertices and e>4v edgesis at least ce3/v2, where c>0 is an absolute constant. This result, known as the 'Crossing Lemma,' has found many important applications in discrete and computational geometry. It is tightup to a multiplicative constant. Here we improve the best known value of the constant by showing that the result holds with c>1024/31827>0.032. The proof has two new ingredients, interesting on their own right. We show that (1) if a graph can be drawn in the plane so that every edge crosses at most 3 others, then its number of edges cannot exceed 5.5(v-2); and (2) the crossing number of any graph is at least 73e - 253(v-2). Both bounds are tight up to anadditive constant (the latter one in the range 4v ≤ e ≤ 5v).

We show that for any $n$ there is an arrangement of $n$ lines which co ntain an $x$-monotone path of length $\Omega(n^{7/4})$.

Article Point sets with many k-sets Share on Author: Géza Tóth Massachusetts Institute of Technology and Hungarian Academy of Sciences Massachusetts Institute of Technology and Hungarian Academy of SciencesView Profile Authors Info & Claims SCG '00: Proceedings of the sixteenth annual symposium on Computational geometryMay 2000 Pages 37–42https://doi.org/10.1145/336154.336171Online:01 May 2000Publication History 14citation382DownloadsMetricsTotal Citations14Total Downloads382Last 12 Months18Last 6 weeks1 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

The crossing number , cr(G) , of a graph G is the least number of crossing points in any drawing of G in the plane. Denote by κ(n,e) the minimum of cr(G) taken over all graphs with n vertices and at least e edges. We prove a conjecture of Erdos os and Guy by showing that κ(n,e)n 2 /e 3 tends to a positive constant as n→∈fty and n l e l n 2 . Similar results hold for graph drawings on any other surface of fixed genus.

A geometric graph is a graph drawn in the plane so that the vertices are represented by points in general position, the edges are represented by straight line segments connecting the corresponding points. Improving a result of Pach and Töröcsik, we show that a geometric graph on n vertices with no k + 1 pairwise disjoint edges has at most k³(n + 1) edges. On the other hand, we construct geometric graphs with n vertices and approximately 3/2 (k - 1)n edges, containing no k + 1 pairwise disjoint edges. We also improve both the lower and upper bounds of Goddard, Katchalski and Kleitman on the maximum number of edges in a geometric graph with no four pairwise disjoint edges.

A drawing of a graph G is a mapping which assigns to each vertex a point of the plane and to each edge a simple continuous arc connecting the corresponding two points. The crossing number of G is the minimum number of crossing points in any drawing of G. We define two new parameters, as follows. The pairwise crossing number (resp. the odd-crossing number) of G is the minimum number of pairs of edges that cross (resp. cross an odd number of times) over all drawings of G. We prove that the determination of each of these parameters is an NP-complete problem. We also prove that the largest of these numbers (the crossing number) cannot exceed twice the square of the smallest (the odd-crossing number). Our proof is based on the following generalization of an old result of Hanani, which is of independent interest. Let G be a graph and let E/sub 0/ be a subset of its edges such that there is a drawing of G, in which every edge belonging E/sub 0/ crosses any other edge an even number of times. Then G can be redrawn so that the element of E/sub 0/ are not involved in any crossing.

It is proved that for n > 3, ⌈25(n − 3)⌉ guards are enough to monitor any simply connected art gallery room of n sides if they are stationed at fixed points and their range of vision is 180°. Furthermore, the position of the guards can be determined by an O(n)-time algorithm.

We show that for any 2-coloring of the ~) segments determined by n points in the plane, one of the color classes contains non-crossing cycles of lengths 3,4,.... [ ~j.This result is tight up to a multiplicative constant.Under the same assumptions, we also prove that there is a non-crossing path of length Q(n2f3), all of whose edges are of the same color.In the special case when the n points are in convex position, we find longer monochromatic non-crossing paths, of length [ ~1.This bound cannot be improved.All of these cycles and paths can be found by O(n2) time algorithms.We also discuss some related problems and generalizations.In particular, we give sharp estimates for the largest number of disjoint monochromatic triangles that can always be selected from our segments.

We prove that among n points in the plane in general position, the shortest distance can occur at most (2+37)n times. We also give a construction where the shortest distance occurs more than (2+516)N−10⌊n⌊ times.

Given a geometric graph, i.e., a collection of segments (edges) between n points in the plane, does it contain a non-crossing configuration of a certain type? It is widely conjectured that all such problems are NP--hard. This has been verified in many special cases, including the existence of a non-crossing spanning tree or k disjoint segments. Here we show that these problems become computationally simpler if we are allowed to choose where to find a non-crossing spanning tree (or k disjoint edges): in the graph or in its complement. We prove that for any 2-coloring of the \\Gamma n 2 \\Delta segments determined by n points in the plane, at least one of the color classes contains a non-crossing spanning tree, and it can be found in O(n log log n+O(1) ) time. Under the same assumptions, we also prove that there exist b n+1 3 c pairwise disjoint segments of the same color, and they can be found with the same efficiency. The nonalgorithmic parts of the above theorems were conjec...