More Like this

1. Multiscale planar graph generation

   https://doi.org/10.1007/s41109-019-0142-3  

   Chauhan, Varsha; Gutfraind, Alexander; Safro, Ilya (December 2019, Applied Network Science)
2. Multiscale Planar Graph Generation

   Varsha Chauhan, Alexander Gutfraind (January 2019, Applied Network Science)
3. Discrete Planar Map Matching

   Fu, Bin; Schweller, Robert; Wylie, Tim (August 2019, Proceedings of the 31st Canadian Conference in Computational Geometry (CCCG 2019))

   Route reconstruction is an important application for Geographic Information Systems (GIS) that rely heavily upon GPS data and other location data from IoT devices. Many of these techniques rely on geometric methods involving the \frechet\ distance to compare curve similarity. The goal of reconstruction, or map matching, is to find the most similar path within a given graph to a given input curve, which is often approximate location data. This process can be approximated by sampling the curves and using the \dfd. Due to power and coverage constraints, the GPS data itself may be sparse causing improper constraints along the edges during the reconstruction if only the continuous \frechet\ distance is used. Here, we look at two variations of discrete map matching: one constraining the walk length and the other limiting the number of vertices visited in the graph. %, and the constraint that the walk may not self-intersect. We give an efficient algorithm to solve the question based on walk length showing it is in \textbf{P}. We prove the other problem is \npc\ and the minimization variant is \apx\ while also giving a parameterized algorithm to solve the problem. 

   more » « less
4. Unitary Anchored Planar Algebras

   https://doi.org/10.1007/s00220-024-04985-w  

   Henriques, André; Penneys, David; Tener, James (May 2024, Communications in Mathematical Physics)

   Abstract In our previous article (http://arxiv.org/abs/1607.06041), we established an equivalence between pointed pivotal module tensor categories and anchored planar algebras. This article introduces the notion of unitarity for both module tensor categories and anchored planar algebras, and establishes the unitary analog of the above equivalence. Our constructions use Baez’s 2-Hilbert spaces (i.e., semisimple$$\textrm{C}^*$$ ${\text{C}}^{\ast }$-categories equipped with unitary traces), the unitary Yoneda embedding, and the notion of unitary adjunction for dagger functors between 2-Hilbert spaces. 

   more » « less
5. 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