TY - CONF AB - A face in a curve arrangement is called popular if it is bounded by the same curve multiple times. Motivated by the automatic generation of curved nonogram puzzles, we investigate possibilities to eliminate the popular faces in an arrangement by inserting a single additional curve. This turns out to be NP-hard; however, it becomes tractable when the number of popular faces is small: We present a probabilistic FPT-approach in the number of popular faces. AU - De Nooijer, Phoebe AU - Terziadis, Soeren AU - Weinberger, Alexandra AU - Masárová, Zuzana AU - Mchedlidze, Tamara AU - Löffler, Maarten AU - Rote, Günter ID - 14888 SN - 0302-9743 T2 - 31st International Symposium on Graph Drawing and Network Visualization TI - Removing popular faces in curve arrangements VL - 14466 ER - TY - CONF AB - A linearly ordered (LO) k-colouring of a hypergraph is a colouring of its vertices with colours 1, … , k such that each edge contains a unique maximal colour. Deciding whether an input hypergraph admits LO k-colouring with a fixed number of colours is NP-complete (and in the special case of graphs, LO colouring coincides with the usual graph colouring). Here, we investigate the complexity of approximating the "linearly ordered chromatic number" of a hypergraph. We prove that the following promise problem is NP-complete: Given a 3-uniform hypergraph, distinguish between the case that it is LO 3-colourable, and the case that it is not even LO 4-colourable. We prove this result by a combination of algebraic, topological, and combinatorial methods, building on and extending a topological approach for studying approximate graph colouring introduced by Krokhin, Opršal, Wrochna, and Živný (2023). AU - Filakovský, Marek AU - Nakajima, Tamio Vesa AU - Opršal, Jakub AU - Tasinato, Gianluca AU - Wagner, Uli ID - 15168 SN - 9783959773119 T2 - 41st International Symposium on Theoretical Aspects of Computer Science TI - Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs VL - 289 ER - TY - JOUR AB - he approximate graph coloring problem, whose complexity is unresolved in most cases, concerns finding a c-coloring of a graph that is promised to be k-colorable, where c≥k. This problem naturally generalizes to promise graph homomorphism problems and further to promise constraint satisfaction problems. The complexity of these problems has recently been studied through an algebraic approach. In this paper, we introduce two new techniques to analyze the complexity of promise CSPs: one is based on topology and the other on adjunction. We apply these techniques, together with the previously introduced algebraic approach, to obtain new unconditional NP-hardness results for a significant class of approximate graph coloring and promise graph homomorphism problems. AU - Krokhin, Andrei AU - Opršal, Jakub AU - Wrochna, Marcin AU - Živný, Stanislav ID - 12563 IS - 1 JF - SIAM Journal on Computing KW - General Mathematics KW - General Computer Science SN - 0097-5397 TI - Topology and adjunction in promise constraint satisfaction VL - 52 ER - TY - JOUR AB - In 1998 Burago and Kleiner and (independently) McMullen gave examples of separated nets in Euclidean space which are non-bilipschitz equivalent to the integer lattice. We study weaker notions of equivalence of separated nets and demonstrate that such notions also give rise to distinct equivalence classes. Put differently, we find occurrences of particularly strong divergence of separated nets from the integer lattice. Our approach generalises that of Burago and Kleiner and McMullen which takes place largely in a continuous setting. Existence of irregular separated nets is verified via the existence of non-realisable density functions ρ:[0,1]d→(0,∞). In the present work we obtain stronger types of non-realisable densities. AU - Dymond, Michael AU - Kaluza, Vojtech ID - 9652 JF - Israel Journal of Mathematics KW - Lipschitz KW - bilipschitz KW - bounded displacement KW - modulus of continuity KW - separated net KW - non-realisable density KW - Burago--Kleiner construction TI - Highly irregular separated nets VL - 253 ER - TY - JOUR AB - A simple drawing D(G) of a graph G is one where each pair of edges share at most one point: either a common endpoint or a proper crossing. An edge e in the complement of G can be inserted into D(G) if there exists a simple drawing of G+e extending D(G). As a result of Levi’s Enlargement Lemma, if a drawing is rectilinear (pseudolinear), that is, the edges can be extended into an arrangement of lines (pseudolines), then any edge in the complement of G can be inserted. In contrast, we show that it is NP-complete to decide whether one edge can be inserted into a simple drawing. This remains true even if we assume that the drawing is pseudocircular, that is, the edges can be extended to an arrangement of pseudocircles. On the positive side, we show that, given an arrangement of pseudocircles A and a pseudosegment σ, it can be decided in polynomial time whether there exists a pseudocircle Φσ extending σ for which A∪{Φσ} is again an arrangement of pseudocircles. AU - Arroyo Guevara, Alan M AU - Klute, Fabian AU - Parada, Irene AU - Vogtenhuber, Birgit AU - Seidel, Raimund AU - Wiedera, Tilo ID - 11999 JF - Discrete and Computational Geometry SN - 0179-5376 TI - Inserting one edge into a simple drawing is hard VL - 69 ER - TY - JOUR AB - Bundling crossings is a strategy which can enhance the readability of graph drawings. In this paper we consider good drawings, i.e., we require that any two edges have at most one common point which can be a common vertex or a crossing. Our main result is that there is a polynomial-time algorithm to compute an 8-approximation of the bundled crossing number of a good drawing with no toothed hole. In general the number of toothed holes has to be added to the 8-approximation. In the special case of circular drawings the approximation factor is 8, this improves upon the 10-approximation of Fink et al. [14]. Our approach also works with the same approximation factor for families of pseudosegments, i.e., curves intersecting at most once. We also show how to compute a 9/2-approximation when the intersection graph of the pseudosegments is bipartite and has no toothed hole. AU - Arroyo Guevara, Alan M AU - Felsner, Stefan ID - 13969 IS - 6 JF - Journal of Graph Algorithms and Applications SN - 1526-1719 TI - Approximating the bundled crossing number VL - 27 ER - TY - THES AB - The extension of extremal combinatorics to the setting of exterior algebra is a work in progress that gained attention recently. In this thesis, we study the combinatorial structure of exterior algebra by introducing a dictionary that translates the notions from the set systems into the framework of exterior algebra. We show both generalizations of celebrated Erdös--Ko--Rado theorem and Hilton--Milner theorem to the setting of exterior algebra in the simplest non-trivial case of two-forms. AU - Köse, Seyda ID - 13331 SN - 2791-4585 TI - Exterior algebra and combinatorics ER - TY - JOUR AB - The celebrated Erdős–Ko–Rado theorem about the maximal size of an intersecting family of r-element subsets of was extended to the setting of exterior algebra in [5, Theorem 2.3] and in [6, Theorem 1.4]. However, the equality case has not been settled yet. In this short note, we show that the extension of the Erdős–Ko–Rado theorem and the characterization of the equality case therein, as well as those of the Hilton–Milner theorem to the setting of exterior algebra in the simplest non-trivial case of two-forms follow from a folklore puzzle about possible arrangements of an intersecting family of lines. AU - Ivanov, Grigory AU - Köse, Seyda ID - 12680 IS - 6 JF - Discrete Mathematics SN - 0012-365X TI - Erdős-Ko-Rado and Hilton-Milner theorems for two-forms VL - 346 ER - TY - JOUR AB - The classical Steinitz theorem states that if the origin belongs to the interior of the convex hull of a set 𝑆⊂ℝ𝑑, then there are at most 2𝑑 points of 𝑆 whose convex hull contains the origin in the interior. Bárány, Katchalski,and Pach proved the following quantitative version of Steinitz’s theorem. Let 𝑄 be a convex polytope in ℝ𝑑 containing the standard Euclidean unit ball 𝐁𝑑. Then there exist at most 2𝑑 vertices of 𝑄 whose convex hull 𝑄′ satisfies 𝑟𝐁𝑑⊂𝑄′ with 𝑟⩾𝑑−2𝑑. They conjectured that 𝑟⩾𝑐𝑑−1∕2 holds with a universal constant 𝑐>0. We prove 𝑟⩾15𝑑2, the first polynomial lower bound on 𝑟. Furthermore, we show that 𝑟 is not greater than 2/√𝑑. AU - Ivanov, Grigory AU - Naszódi, Márton ID - 14660 JF - Bulletin of the London Mathematical Society SN - 0024-6093 TI - Quantitative Steinitz theorem: A polynomial bound ER - TY - JOUR AB - The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r−1)+1 points in Rd, one can find a partition X=X1∪⋯∪Xr of X, such that the convex hulls of the Xi, i=1,…,r, all share a common point. In this paper, we prove a trengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span ⌊n/3⌋ vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Álvarez-Rebollar et al. guarantees ⌊n/6⌋pairwise crossing triangles. Our result generalizes to a result about simplices in Rd, d≥2. AU - Fulek, Radoslav AU - Gärtner, Bernd AU - Kupavskii, Andrey AU - Valtr, Pavel AU - Wagner, Uli ID - 13974 JF - Discrete and Computational Geometry SN - 0179-5376 TI - The crossing Tverberg theorem ER -