More Like this

1. Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems

   https://doi.org/10.1137/1.9781611975482.66  

   Eli Fox-Epstein, Eli Klein (March 2019, Proceedings of the Thirtieth Annual {ACM-SIAM} Symposium on Discrete Algorithms)

   We show that, for any ∊ > 0, there is a deterministic embedding of edge-weighted planar graphs of diameter D into bounded-treewidth graphs. The embedding has additive error ∊D. We use this construction to obtain the first efficient bicriteria approximation schemes for weighted planar graphs addressing k-Center (equivalently d-Domination), and a metric generalization of independent set, d-independent SET. The approximation schemes employ a metric generalization of Baker's framework that is based on our embedding result. 

   more » « less
2. Rigidity and continuous extension for conformal maps of circle domains

   https://doi.org/10.1090/tran/8923  

   Ntalampekos, Dimitrios (July 2023, Transactions of the American Mathematical Society)

   We present sufficient conditions so that a conformal map between planar domains whose boundary components are Jordan curves or points has a continuous or homeomorphic extension to the closures of the domains. Our conditions involve the notions of cofat domains and C N E D CNED sets, i.e., countably negligible for extremal distances, recently introduced by the author. We use this result towards establishing conformal rigidity of a class of circle domains. A circle domain is conformally rigid if every conformal map onto another circle domain is the restriction of a Möbius transformation. We show that circle domains whose point boundary components are C N E D CNED are conformally rigid. This result is the strongest among all earlier works and provides substantial evidence towards the rigidity conjecture of He–Schramm [Invent. Math. 115 (1994), no. 2, 297–310], relating the problems of conformal rigidity and removability. 

   more » « less
3. New hardness results for planar graph problems in p and an algorithm for sparsest cut

   https://doi.org/10.1145/3357713.3384310  

   Abboud, Amir; Cohen-Addad, Vincent; Klein, Philip N. (June 2020, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing)

   null (Ed.)

   The Sparsest Cut is a fundamental optimization problem that have been extensively studied. For planar inputs the problem is in P and can be solved in Õ(n 3 ) time if all vertex weights are 1. Despite a significant amount of effort, the best algorithms date back to the early 90’s and can only achieve O(log n)-approximation in Õ(n) time or 3.5-approximation in Õ(n 2 ) time [Rao, STOC92]. Our main result is an Ω(n 2−ε ) lower bound for Sparsest Cut even in planar graphs with unit vertex weights, under the (min, +)-Convolution conjecture, showing that approxima- tions are inevitable in the near-linear time regime. To complement the lower bound, we provide a 3.3-approximation in near-linear time, improving upon the 25-year old result of Rao in both time and accuracy. We also show that our lower bound is not far from optimal by observing an exact algorithm with running time Õ(n 5/2 ) improving upon the Õ(n 3 ) algorithm of Park and Phillips [STOC93]. Our lower bound accomplishes a repeatedly raised challenge by being the first fine-grained lower bound for a natural planar graph problem in P. Building on our construction we prove near-quadratic lower bounds under SETH for variants of the closest pair problem in planar graphs, and use them to show that the popular Average-Linkage procedure for Hierarchical Clustering cannot be simulated in truly subquadratic time. At the core of our constructions is a diamond-like gadget that also settles the complexity of Diameter in distributed planar networks. We prove an Ω(n/ log n) lower bound on the number of communication rounds required to compute the weighted diameter of a network in the CONGET model, even when the underlying graph is planar and all nodes are D = 4 hops away from each other. This is the first poly(n) lower bound in the planar-distributed setting, and it complements the recent poly(D, log n) upper bounds of Li and Parter [STOC 2019] for (exact) unweighted diameter and for (1 + ε) approximate weighted diameter. 

   more » « less
4. On fillings of $$\partial (V\times {\mathbb {D}})$$

   https://doi.org/10.1007/s00208-022-02373-0  

   Zhou, Zhengyi (February 2022, Mathematische Annalen)

   Abstract We show that any symplectically aspherical/Calabi–Yau filling of Y := ∂(V × D) has vanishing symplectic cohomology for any Liouville domain V . In particular, we make no topological requirement on the filling and c₁(V ) can be nonzero. Moreover, we show that for any symplectically aspherical/Calabi–Yau filling W of Y , the interior W˚ is diffeomorphic to the interior of V × D if π₁(Y ) is abelian and dim V ≥ 4. And W is diffeomorphic to V × D if moreover the Whitehead group of π₁(Y ) is trivial. 

   more » « less
5. Grand-Schnyder Woods

   https://doi.org/10.1007/s00026-024-00729-8  

   Bernardi, Olivier; Fusy, Éric; Liang, Shizhe (November 2024, Annals of Combinatorics)

   We define a far-reaching generalization of Schnyder woods which encompasses many classical combinatorial structures on planar graphs. Schnyder woods are defined for planar triangulations as certain triples of spanning trees covering the triangulation and crossing each other in an orderly fashion. They are of theo- retical and practical importance, as they are central to the proof that the order dimension of any planar graph is at most 3, and they are also underlying an elegant drawing algorithm. In this article we extend the concept of Schnyder wood well beyond its original setting: for any integer d ≥ 3 we define a “grand-Schnyder” structure for (embedded) planar graphs which have faces of degree at most d and non-facial cycles of length at least d. We prove the existence of grand-Schnyder structures, provide a linear construction algorithm, describe 4 different incarnations (in terms of tuples of trees, corner labelings, weighted orientations, and marked orientations), and define a lattice for the set of grand Schnyder structures of a given planar graph. We show that the grand-Schnyder framework unifies and extends several clas- sical constructions: Schnyder woods and Schnyder decompositions, regular edge-labelings (a.k.a. transversal structures), and Felsner woods. 

   more » « less