Search

We study dynamic planar graphs with n vertices, subject to edge deletion, edge contraction, edge insertion across a face, and the splitting of a vertex in specified corners. We dynamically maintain a combinatorial embedding of such a planar graph, subject to connectivity and 2-vertex-connectivity (biconnectivity) queries between pairs of vertices. Whenever a query pair is connected and not biconnected, we find the first and last cutvertex separating them. Additionally, we allow local changes to the embedding by flipping the embedding of a subgraph that is connected by at most two vertices to the rest of the graph. We support all queries and updates in deterministic, worst-case, O(log2 n) time, using an O(n)-sized data structure.

The top tree data structure is an important and fundamental tool in dynamic graph algorithms. Top trees have existed for decades, and today serve as an ingredient in many state-of-the-art algorithms for dynamic graphs. In this work, we give a new direct proof of the existence of top trees, facilitating simpler and more direct implementations of top trees, based on ideas from splay trees. This result hinges on new insights into the structure of top trees, and in particular the structure of each root path in a top tree.

We study dynamic planar graphs with n vertices, subject to edge deletion, edge contraction, edge insertion across a face, and the splitting of a vertex in specified corners. We dynamically maintain a combinatorial embedding of such a planar graph, subject to connectivity and 2-vertex-connectivity (biconnectivity) queries between pairs of vertices. Whenever a query pair is connected and not biconnected, we find the first and last cutvertex separating them. Additionally, we allow local changes to the embedding by flipping the embedding of a subgraph that is connected by at most two vertices to the rest of the graph. We support all queries and updates in deterministic, worst-case, O(log² n) time, using an O(n)-sized data structure.

In this thesis we study the Euclidean Shortest Path Problem (ESPP), the problem of finding a shortest path between two points in the plane among a set of polygonal obstacles. Recently, Du et al. (2023) proposed an algorithm based on hub labelling where, in a preprocessing step, a uniform grid is superimposed on the plane in which each cell contains the hub labels from obstacle vertices with visibility to it. We propose an alternative planar subdivision that we call a visibility subdivision, which has the desirable properties that (1) all points in the same region can see the same set of obstacle vertices and (2) no other subdivision satisfying (1) has fewer regions. In addition, we propose a set of techniques that we collectively call hierarchical compression for reducing the space consumption of the hub labels. Visibility subdivisions show promising experimental results but additional optimizations are required to make them competitive with the highest-resolution grid employed by Du et al. (2023). Likewise, the employment of hierarchical compression in the same experimental setting exhibits a remarkable reduction in the space consumption of hub labels in visibility subdivisions but incurs a penalty in the form of a minor increase in query times. Finally, we present the results of our work prior to the revision of our objective induced by the aforementioned work by Du et al. (2023). This includes a revised theoretical description of the ESPP algorithm Polyanya(Cui et al., 2017) and the proposal of an algorithm called Neighborhood Search which, using preprocessing, reports for a query point the set of obstacle vertices visible from that point. Experimental results suggest that in its current form, Neighborhood Search is inferior to competing algorithms.

The top tree data structure is an important and fundamental tool in dynamic graph algorithms. Top trees have existed for decades, and today serve as an ingredient in many state-of-the-art algorithms for dynamic graphs. In this work, we give a new direct proof of the existence of top trees, facilitating simpler and more direct implementations of top trees, based on ideas from splay trees. This result hinges on new insights into the structure of top trees, and in particular the structure of each root path in a top tree. In amortized analysis, our top trees match the asymptotic bounds of the state of the art.

We study dynamic planar graphs with n vertices, subject to edge deletion, edge contraction, edge insertion across a face, and the splitting of a vertex in specified corners. We dynamically maintain a combinatorial embedding of such a planar graph, subject to connectivity and 2-vertex-connectivity (biconnectivity) queries between pairs of vertices. Whenever a query pair is connected and not biconnected, we find the first and last cutvertex separating them. Additionally, we allow local changes to the embedding by flipping the embedding of a subgraph that is connected by at most two vertices to the rest of the graph. We support all queries and updates in deterministic, worst-case, O(log2 n) time, using an O(n)-sized data structure.

Human gut microbiota produce a variety of molecules, some of which enter the bloodstream and impact health. Conversely, dietary or pharmacological compounds may affect the microbiota before entering the circulation. Characterization of these interactions is an important step towards understanding the effects of the gut microbiota on health. In this cross-sectional study, we used deep metagenomic sequencing and ultra-high-performance liquid chromatography linked to mass spectrometry for a detailed characterization of the gut microbiota and plasma metabolome, respectively, of 8583 participants invited at age 50 to 64 from the population-based Swedish CArdioPulmonary bioImage Study. Here, we find that the gut microbiota explain up to 58% of the variance of individual plasma metabolites and we present 997 associations between alpha diversity and plasma metabolites and 546,819 associations between specific gut metagenomic species and plasma metabolites in an online atlas (https://gutsyatlas.serve.scilifelab.se/). We exemplify the potential of this resource by presenting novel associations between dietary factors and oral medication with the gut microbiome, and microbial species strongly associated with the uremic toxin p-cresol sulfate. This resource can be used as the basis for targeted studies of perturbation of specific metabolites and for identification of candidate plasma biomarkers of gut microbiota composition.

Here, we present a longitudinal shotgun sequencing metagenomics study of 16 healthy, Danish women in the reproductive age. The aim of the study was to investigate whether lactobacilli, orally consumed, had any impact on the vaginal microbiome and its functional potential. The 16 women aged 19–45 years were recruited from Copenhagen, Denmark. One baseline vaginal sample (Day 0) and two study samples (Days 25–30 and Days 55–60, respectively), were sampled. The vaginal samples were analyzed by shotgun metagenomics. We detected 26 species in the vaginal microbiota of the 16 women, of which six belonged to the Lactobacillus genus. We observed three vaginal microbiome clusters mainly dominated by Gardnerella vaginalis, Lactobacillus iners, or Lactobacillus crispatus. The oral probiotic had no detectable effect on either the composition or the functional potential of the vaginal microbiota. Most of the study subjects (11 out of 16 women) exhibited only minor changes in the vaginal microbiome during the treatment with probiotics. Any compositional changes could not be associated to the probiotic treatment. Future studies may benefit from an increased number of participants, and administration of the probiotics during conditions with bacterial imbalance (e.g., during/after antibiotic treatment) or the use of different Lactobacillus spp. known to colonize the vagina.