More Like this

1. Drawing Planar Graphs and 1-Planar Graphs Using Cubic Bézier Curves with Bounded Curvature

   https://doi.org/10.4230/LIPIcs.GD.2024.39  

   Eppstein, David; Goodrich, Michael T; Illickan, Abraham M (October 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Felsner, Stefan; Klein, Karsten (Ed.)

   We study algorithms for drawing planar graphs and 1-planar graphs using cubic Bézier curves with bounded curvature. We show that any n-vertex 1-planar graph has a 1-planar RAC drawing using a single cubic Bézier curve per edge, and this drawing can be computed in O(n) time given a combinatorial 1-planar drawing. We also show that any n-vertex planar graph G can be drawn in O(n) time with a single cubic Bézier curve per edge, in an O(n)× O(n) bounding box, such that the edges have Θ(1/degree(v)) angular resolution, for each v ∈ G, and O(√n) curvature. 

   more » « less
2. Algorithms for Intersection Graphs of t-Intervals and t-Pseudodisks

   Chekuri, Chandra; Inamdar, Tanmay (June 2022, Theory of computing)

   Intersection graphs of planar geometric objects such as intervals, disks, rectangles and pseudodisks are well-studied. Motivated by various applications, Butman et al. (ACM Trans. Algorithms, 2010) considered algorithmic questions in intersection graphs of $$t$$-intervals. A $$t$$-interval is a union of $$t$$ intervals --- these graphs are also referred to as multiple-interval graphs. Subsequent work by Kammer et al.\ (APPROX-RANDOM 2010) considered intersection graphs of $$t$$-disks (union of $$t$$ disks), and other geometric objects. In this paper we revisit some of these algorithmic questions via more recent developments in computational geometry. For the \emph{minimum-weight dominating set problem} in $$t$$-interval graphs, we obtain a polynomial-time $$O(t \log t)$$-approximation algorithm, improving upon the previously known polynomial-time $t^2$-approximation by Butman et al. In the same class of graphs we show that it is $$\NP$$-hard to obtain a $$(t-1-\epsilon)$$-approximation for any fixed $$t \ge 3$$ and $$\epsilon > 0$$. The approximation ratio for dominating set extends to the intersection graphs of a collection of $$t$$-pseudodisks (nicely intersecting $$t$$-tuples of closed Jordan domains). We obtain an $$\Omega(1/t)$$-approximation for the \emph{maximum-weight independent set} in the intersection graph of $$t$$-pseudodisks in polynomial time. Our results are obtained via simple reductions to existing algorithms by appropriately bounding the union complexity of the objects under consideration. 

   more » « less
3. Planar and poly-arc Lombardi drawings

   https://doi.org/https://doi.org/10.20382/jocg.v9i1a11  

   Duncan, Christian A.; Eppstein, David; Goodrich, Michael T.; Kobourov, Stephen G.; Löffler, Maarten; Nöllenburg, Martin (January 2018, Journal of computational geometry)

   In Lombardi drawings of graphs, edges are represented as circular arcs and the edges incident on vertices have perfect angular resolution. It is known that not every planar graph has a planar Lombardi drawing. We give an example of a planar 3-tree that has no planar Lombardi drawing and we show that all outerpaths do have a planar Lombardi drawing. Further, we show that there are graphs that do not even have any Lombardi drawing at all. With this in mind, we generalize the notion of Lombardi drawings to that of (smooth) k-Lombardi drawings, in which each edge may be drawn as a (differentiable) sequence of k circular arcs; we show that every graph has a smooth 2-Lombardi drawing and every planar graph has a smooth planar 3-Lombardi drawing. We further investigate related topics connecting planarity and Lombardi drawings. 

   more » « less
4. On the Biplanarity of Blowups

   https://doi.org/10.7155/jgaa.v28i2.2989  

   Eppstein, David (May 2024, Journal of Graph Algorithms and Applications)

   The 2-blowup of a graph is obtained by replacing each vertex with two non-adjacent copies; a graph is biplanar if it is the union of two planar graphs. We disprove a conjecture of Gethner that 2-blowups of planar graphs are biplanar: iterated Kleetopes are counterexamples. Additionally, we construct biplanar drawings of 2-blowups of planar graphs whose duals have two-path induced path partitions, and drawings with split thickness two of 2-blowups of 3-chromatic planar graphs, and of graphs that can be decomposed into a Hamiltonian path and a dual Hamiltonian path. 

   more » « less
5. A Dynamic Programming Framework for Generating Approximately Diverse and Optimal Solutions

   Gálvez, Waldo; Goswami, Mayank; Merino, Arturo; Park, GiBeom; Tsai, Meng-Tsung; Verdugo, Victor (January 2025, Arxiv)

   We develop a general framework, called approximately-diverse dynamic programming (ADDP) that can be used to generate a collection of k≥2 maximally diverse solutions to various geometric and combinatorial optimization problems. Given an approximation factor 0≤c≤1, this framework also allows for maximizing diversity in the larger space of c-approximate solutions. We focus on two geometric problems to showcase this technique: 1. Given a polygon P, an integer k≥2 and a value c≤1, generate k maximally diverse c-nice triangulations of P. Here, a c-nice triangulation is one that is c-approximately optimal with respect to a given quality measure σ. 2. Given a planar graph G, an integer k≥2 and a value c≤1, generate k maximally diverse c-optimal Independent Sets (or, Vertex Covers). Here, an independent set S is said to be c-optimal if |S|≥c|S′| for any independent set S′ of G. Given a set of k solutions to the above problems, the diversity measure we focus on is the average distance between the solutions, where d(X,Y)=|XΔY|. For arbitrary polygons and a wide range of quality measures, we give poly(n,k) time (1−Θ(1/k))-approximation algorithms for the diverse triangulation problem. For the diverse independent set and vertex cover problems on planar graphs, we give an algorithm that runs in time 2^(O(k.δ^(−1).ϵ^(−2)).n^O(1/ϵ) and returns (1−ϵ)-approximately diverse (1−δ)c-optimal independent sets or vertex covers. Our triangulation results are the first algorithmic results on computing collections of diverse geometric objects, and our planar graph results are the first PTAS for the diverse versions of any NP-complete problem. Additionally, we also provide applications of this technique to diverse variants of other geometric problems. 

   more » « less