More Like this

1. Minimum Plane Bichromatic Spanning Trees

   https://doi.org/10.4230/LIPIcs.ISAAC.2024.4  

   A_Akitaya, Hugo; Biniaz, Ahmad; Demaine, Erik D; Kleist, Linda; Stock, Frederick; Tóth, Csaba D (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Mestre, Julián; Wirth, Anthony (Ed.)

   For a set of red and blue points in the plane, a minimum bichromatic spanning tree (MinBST) is a shortest spanning tree of the points such that every edge has a red and a blue endpoint. A MinBST can be computed in O(n log n) time where n is the number of points. In contrast to the standard Euclidean MST, which is always plane (noncrossing), a MinBST may have edges that cross each other. However, we prove that a MinBST is quasi-plane, that is, it does not contain three pairwise crossing edges, and we determine the maximum number of crossings. Moreover, we study the problem of finding a minimum plane bichromatic spanning tree (MinPBST) which is a shortest bichromatic spanning tree with pairwise noncrossing edges. This problem is known to be NP-hard. The previous best approximation algorithm, due to Borgelt et al. (2009), has a ratio of O(√n). It is also known that the optimum solution can be computed in polynomial time in some special cases, for instance, when the points are in convex position, collinear, semi-collinear, or when one color class has constant size. We present an O(log n)-factor approximation algorithm for the general case. 

   more » « less
2. The effect of adding randomly weighted edges

   https://doi.org/10.1137/20M1335418  

   Frieze, A. (January 2021, SIAM journal on discrete mathematics)

   We consider the following question. We have a dense regular graph $$G$$ with degree $$\a n$$, where $$\a>0$$ is a constant. We add $m=o(n^2)$ random edges. The edges of the augmented graph $G(m)$ are given independent edge weights $$X(e),e\in E(G(m))$$. We estimate the minimum weight of some specified combinatorial structures. We show that in certain cases, we can obtain the same estimate as is known for the complete graph, but scaled by a factor $$\a^{-1}$$. We consider spanning trees, shortest paths and perfect matchings in (pseudo-random) bipartite graphs. 

   more » « less
3. Reconstruction of the Crossing Type of a Point Set from the Compatible Exchange Graph of Noncrossing Spanning Trees

   https://doi.org/10.1007/978-3-030-14085-4_19  

   Marcos Oropeza, Csaba D. (February 2019, International Conference on Discrete Geometry for Computer Imagery)

   Let P be a set of n points in the plane in general position. The order type of P specifies, for every ordered triple, a positive or negative orientation; and the x-type (a.k.a. crossing type) of P specifies, for every unordered 4-tuple, whether they are in convex position. Geometric algorithms on P typically rely on primitives involving the order type or x-type (i.e., triples or 4-tuples). In this paper, we show that the x-type of P can be reconstructed from the compatible exchange graph G1(P) of noncrossing spanning trees on P. This extends a recent result by Keller and Perles (2016), who proved that the x-type of P can be reconstructed from the exchange graph G0(P) of noncrossing spanning trees, where G1(P) is a subgraph of G0(P) . A crucial ingredient of our proof is a structure theorem on the maximal sets of pairwise noncrossing edges (msnes) between two components of a planar straight-line graph on the point set P. 

   more » « less
4. Packing Trees into 1-Planar Graphs

   https://doi.org/10.1007/978-3-030-39881-1_8  

   De Luca, F.; Di Giacomo, E.; Hong, S.; Kobourov, S.; Lenhart, W.; Liotta, G.; Meijer, H.; Tappini, A.; Wismath, S. (January 2020, 14th International Conference and Workshop on Algorithms and Computation (WALCOM))

   We introduce and study the 1-planar packing problem: Given k graphs with n vertices 𝐺1,…,𝐺𝑘, find a 1-planar graph that contains the given graphs as edge-disjoint spanning subgraphs. We mainly focus on the case when each 𝐺𝑖 is a tree and 𝑘=3 . We prove that a triple consisting of three caterpillars or of two caterpillars and a path may not admit a 1-planar packing, while two paths and a special type of caterpillar always have one. We then study 1-planar packings with few crossings and prove that three paths (resp. cycles) admit a 1-planar packing with at most seven (resp. fourteen) crossings. We finally show that a quadruple consisting of three paths and a perfect matching with 𝑛≥12 vertices admits a 1-planar packing, while such a packing does not exist if 𝑛≤10 . 

   more » « less
5. Non-Crossing Hamiltonian Paths and Cycles in Output-Polynomial Time

   https://doi.org/10.4230/LIPIcs.SoCG.2023.29  

   Eppstein, David (January 2023, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Chambers, Erin W; Gudmundsson, Joachim (Ed.)

   We show that, for planar point sets, the number of non-crossing Hamiltonian paths is polynomially bounded in the number of non-crossing paths, and the number of non-crossing Hamiltonian cycles (polygonalizations) is polynomially bounded in the number of surrounding cycles. As a consequence, we can list the non-crossing Hamiltonian paths or the polygonalizations, in time polynomial in the output size, by filtering the output of simple backtracking algorithms for non-crossing paths or surrounding cycles respectively. To prove these results we relate the numbers of non-crossing structures to two easily-computed parameters of the point set: the minimum number of points whose removal results in a collinear set, and the number of points interior to the convex hull. These relations also lead to polynomial-time approximation algorithms for the numbers of structures of all four types, accurate to within a constant factor of the logarithm of these numbers. 

   more » « less