Search

We study the complexity of testing whether a biconnected graph G = (V , E) is planar with the constraint that some cyclic orders of the edges incident to its vertices are allowed while some others are forbidden. The allowed cyclic orders are described by associating every vertex v of G with a set D (v) of FPQ-trees. Let tw be the treewidth of G and let D max be the maximum number of FPQ-trees per vertex. We show that the problem is FPT when parameterized by tw + D max , paraNP-hard when parameterized by D max , and W[1]-hard when parameterized by tw. We also consider NodeTrix planar representations of clustered graphs, where clusters are adjacency matrices and inter-cluster edges are non-intersecting simple curves. We prove that NodeTrix planarity with fixed sides is FPT when parameterized by the size of clusters plus the treewidth of the graph obtained by collapsing clusters to single vertices, provided that this graph is biconnected. [ABSTRACT FROM AUTHOR]

The planar slope number of a planar graph G is the minimum integer k such that G admits a planar drawing with vertices as points and edges as straight-line segments with k distinct slopes. Similarly, a plane slope number is defined for a plane graph, where a fixed combinatorial embedding of the graph is given and the output must respect the given embedding. We prove tight bounds (up to a small multiplicative or additive constant) for the plane and the planar slope numbers of partial 2-trees of bounded degree. We also answer a long standing question by Garg and Tamassia (In: van Leeuwen J (eds) Proceedings of the Second Annual European Symposium on Algorithms (ESA), LNCS, vol 855, pp 12–23, Springer, 1994) on the angular resolution of the planar straight-line drawings of series-parallel graphs of bounded degree. [ABSTRACT FROM AUTHOR]

Given a graph G and an integer b , OrthogonalPlanarity is the problem of testing whether G admits a planar orthogonal drawing with at most b bends. OrthogonalPlanarity is known to be NP -complete. We show that this problem belongs to the XP class when parameterized by treewidth. The proof exploits a fixed-parameter tractable approach that uses two more parameters besides treewidth, namely the natural parameter b and the number of vertices with degree at most two of G. Such approach is based on the new concept of sketched orthogonal representation, which synthetically describes a family of equivalent orthogonal drawings. The approach is general enough to be applicable to other related problems, namely HV-Planarity and FlexDraw. Also, in the special case of series-parallel graphs we obtain that both OrthogonalPlanarity and HV-Planarity can be solved in O (n 3 log ⁡ n) time, which improves on the previous O (n 4) bounds for these two. [ABSTRACT FROM AUTHOR]

Background: The COVID-19 epidemic in Italy has severely affected people aged more than 80, especially socially isolated. Aim of this paper is to assess whether a social and health program reduced mortality associated to the epidemic. Methods: An observational retrospective cohort analysis of deaths recorded among >80 years in three Italian cities has been carried out to compare death rate of the general population and "Long Live the Elderly!" (LLE) program. Parametric and non-parametric tests have been performed to assess differences of means between the two populations. A multivariable analysis to assess the impact of covariates on weekly mortality has been carried out by setting up a linear mixed model. Results: The total number of services delivered to the LLE population (including phone calls and home visits) was 34,528, 1 every 20 day per person on average, one every 15 days during March and April. From January to April 2019, the same population received one service every 41 days on average, without differences between January-February and March-April. The January-April 2020 cumulative crude death rate was 34.8‰ (9,718 deaths out of 279,249 individuals; CI95%: 34.1–35.5) and 28.9‰ (166 deaths out of 5,727 individuals; CI95%:24.7–33.7) for the general population and the LLE sample respectively. The general population weekly death rate increased after the 11th calendar week that was not the case among the LLE program participants (p<0.001). The Standardized Mortality Ratio was 0.83; (CI95%: 0.71–0.97). Mortality adjusted for age, gender, COVID-19 weekly incidence and prevalence of people living in nursing homes was lower in the LLE program than in the general population (p<0.001). Conclusions: LLE program is likely to limit mortality associated with COVID-19. Further studies are needed to establish whether it is due to the impact of social care that allows a better clients' adherence to the recommendations of physical distancing or to an improved surveillance of older adults that prevents negative outcomes associated with COVID-19. [ABSTRACT FROM AUTHOR]

We introduce and study a constrained planarity testing problem, called 1 -Fixed Constrained Planarity , and prove that this problem can be solved in quadratic time for biconnected graphs. Our solution is based on a novel definition of fixedness that makes it possible to simplify and extend known techniques about Simultaneous PQ-Ordering. We exploit this result to study different versions of the hybrid planarity testing problem. Namely, we show polynomial-time solutions for a variant of NodeTrix Planarity with fixed sides, for PolyLink Planarity , and for Clique Planarity with fixed sides. [ABSTRACT FROM AUTHOR]

An ortho-polygon visibility representation (OPVR) of an embedded graph G is an embedding-preserving drawing that maps each vertex of G to a distinct orthogonal polygon and each edge of G to a vertical or horizontal visibility between its end-vertices. An OPVR Γ has vertex complexity k if every polygon of Γ has at most k reflex corners. A 1-plane graph is an embedded graph such that each edge is crossed at most once. It is known that 3-connected 1-plane graphs admit an OPVR with vertex complexity at most 12, while vertex complexity at least 2 may be required in some cases. In this paper, we reduce this gap by showing that vertex complexity 5 is always sufficient, while vertex complexity 4 may be sometimes required. These results are based on the study of the combinatorial properties of the B-, T-, and W-configurations in 3-connected 1-plane graphs. An implication of the upper bound is the existence of a O ˜ (n 10 7 ) -time drawing algorithm that computes an OPVR of an n -vertex 3-connected 1-plane graph on an integer grid of size O (n) × O (n) and with vertex complexity at most 5. [ABSTRACT FROM AUTHOR]

Italy was one of the first European countries affected by the new coronavirus (COVID-19) pandemic, with over 105,000 infected people and close to 13,000 deaths, until March 31st. The pandemic has hit especially hard because of the country's demographic structure, with a high percentage of older adults. The authors explore the possibility, recently aired in some studies, of extensive intergenerational contact as a possible determinant of the severity of the pandemic among the older Italian adults. We analyzed several variables to test this hypothesis, such as the percentage of infected patients aged >80 years, available nursing home beds, COVID-19 incidence rate, and the number of days from when the number of positive tests exceeded 50 (epidemic maturity). We also included in the analysis mean household size and percentage of households comprising one person, in the region. Paradoxically, the results are opposite of what was previously reported. The pandemic was more severe in regions with higher family fragmentation and increased availability of residential health facilities. [ABSTRACT FROM AUTHOR]

Graph Drawing Beyond Planarity is a rapidly growing research area that classifies and studies geometric representations of nonplanar graphs in terms of forbidden crossing configurations. The aim of this survey is to describe the main research directions in this area, the most prominent known results, and some of the most challenging open problems. [ABSTRACT FROM AUTHOR]

We study the NodeTrix planarity testing problem for flat clustered graphs when the maximum size of each cluster is bounded by a constant k. We consider both the case when the sides of the matrices to which the edges are incident are fixed and the case when they can be chosen arbitrarily. We show that NodeTrix planarity testing with fixed sides can be solved in O (k 3 k + 3 2 · n) time for every flat clustered graph that can be reduced to a partial 2-tree by collapsing its clusters into single vertices. In the general case, NodeTrix planarity testing with fixed sides can be solved in O(n) time for k = 2 , but it is NP-complete for any k > 2 . NodeTrix planarity testing remains NP-complete also in the free sides model when k > 4 . [ABSTRACT FROM AUTHOR]

Let Γ be a straight-line drawing of a graph and let u and v be two vertices of Γ. The Gabriel disk of u , v is the disk having u and v as antipodal points. A pair 〈 Γ 0 , Γ 1 〉 of vertex-disjoint straight-line drawings forms a mutual witness Gabriel drawing when, for i = 0 , 1 , any two vertices u and v of Γ i are adjacent if and only if their Gabriel disk does not contain any vertex of Γ 1 − i. We characterize the pairs 〈 G 0 , G 1 〉 of complete bipartite graphs that admit a mutual witness Gabriel drawing. The characterization leads to a linear time testing algorithm. We also show that when the pair 〈 G 0 , G 1 〉 consists of two complete multi-partite graphs whose partition sets all have size greater than one, then the pair does not admit a mutual witness Gabriel drawing unless the pair is 〈 K 2 , 2 , K 2 , 2 〉. [ABSTRACT FROM AUTHOR]

Background: The increasing burden of chronic diseases associated with the ageing of the European population constitutes one of the main challenges for the welfare systems in developed western countries, especially through its impact on the use of hospital services and the cost of care. This study aims at evaluating the cost of hospital care for older adults living in the Lazio Region, Italy, according to their level of frailty. Methods: Since 2014 a longitudinal randomized cohort study has been carried out on a sample consisting of 1280 older adults aged over 64 years resident in the Lazio region (Italy), with their being evaluated for multidimensional frailty. Accesses to Hospital Services (acute care and Day Hospital care admissions and Emergency Room accesses) during the first year after enrolment, as well as the related costs have been recorded through a regional database. Costs have been stratified on the basis of the state of frailty. Results: The analysis of hospital services and costs highlights the role played by pre-frail individuals who generated 49.3% of the hospital care cumulative costs. Hospital Admission (HA) costs arising from robust and pre-frail subjects are 70% of the total HA costs. Pre-frail individuals also showed the highest average HA cost per person/year (7062.89 Euros). The main determinant of the highest HA costs was given by the number of HAs during the follow-up (multivariate linear regression, ß coefficient = 0.319; p<0.001), which was higher among pre-frail individuals than in any other group of patients. Conclusions: Pre-frail individuals generated the highest cost for hospital care in a sample of representative subjects living in an Italian Region with a low rate of community care services, as is the case in the Lazio region. Assessment of the multidimensional frailty of older adults permits a better definition of the important target of the pre-frail population as the main category within which interventions to prevent or mitigate frailty should be carried out. [ABSTRACT FROM AUTHOR]

Abstract An HV-graph is a planar graph with vertex-degree at most four such that each edge is labeled either H (horizontal) or V (vertical). The HV-planarity testing problem asks whether an HV-graph admits an HV-drawing , that is, a planar drawing such that each edge with label H is drawn as a horizontal segment and each edge with label V is drawn as a vertical segment. We prove that the HV-planarity testing problem is NP-complete even for graphs with vertex-degree at most three, which answers an open question posed by both Manuch et al. [30] and Durocher et al. [17]. On the positive side, we prove that the HV-planarity testing problem can be solved in polynomial-time for series-parallel graphs. This result significantly extends a previous result by Durocher et al. about HV-planarity testing of biconnected outerplanar graphs of maximum vertex-degree three. Highlights • HV-planarity testing is NP-complete, even for graphs with vertex-degree at most 3. • Polynomial-time HV-planarity testing for 2-connected series-parallel graphs. • Polynomial-time HV-planarity testing for partial 2-trees. [ABSTRACT FROM AUTHOR]

A (weak) rectangle visibility representation, or simply an RVR, of a graph consists of an assignment of axis-aligned rectangles to vertices such that for every edge there exists a horizontal or vertical line of sight between the rectangles assigned to its endpoints. Given a graph with a fixed embedding in the plane, we show that the problem of testing whether this graph has an embedding-preserving RVR can be solved in polynomial time for general embedded graphs and in linear time for 1-plane graphs, i.e., for embedded graphs having at most one crossing per edge. The linear time algorithm uses three forbidden configurations, which extend the set known for straight-line drawings of 1-plane graphs. The algorithm first checks for the presence of these forbidden configurations in the input graph, and then either an embedding-preserving RVR is computed (also in linear time) or a forbidden configuration is reported as a negative witness. Finally, we discuss extensions of our study to the case when the embedding is not fixed but the RVR can have at most one crossing per edge. [ABSTRACT FROM AUTHOR]

A subcubic planar graph is a planar graph whose vertices have degree at most 3. We show that the subcubic planar graphs with at least five vertices have planar slope number at most 4, which is worst-case optimal. This answers an open question by Jelínek et al. [10] . Furthermore, we prove that the subcubic planar graphs with at least five vertices have angular resolution π / 4 , which solves an open problem by Kant [11] and by Formann et al. [8] . [ABSTRACT FROM AUTHOR]

A planar orthogonal drawing of a planar 4-graph G (i.e., a planar graph with vertex-degree at most four) is a crossing-free drawing that maps each vertex of G to a distinct point of the plane and each edge of G to a polygonal chain consisting of horizontal and vertical segments. A longstanding open question in Graph Drawing, dating back over 30 years, is whether there exists a linear-time algorithm to compute an orthogonal drawing of a plane 4-graph with the minimum number of bends. The term "plane" indicates that the input graph comes together with a planar embedding, which must be preserved by the drawing (i.e., the drawing must have the same set of faces as the input graph). In this paper we positively answer the question above for the widely-studied class of series–parallel graphs. Our linear-time algorithm is based on a characterization of the planar series–parallel graphs that admit an orthogonal drawing without bends. This characterization is given in terms of the orthogonal spirality that each type of triconnected component of the graph can take; the orthogonal spirality of a component measures how much that component is "rolled-up" in an orthogonal drawing of the graph. [ABSTRACT FROM AUTHOR]

Antiretroviral therapy has been shown to reduce rates of congenital CMV infection. Little information is available on the possible impact of antiretroviral therapy on postnatal breastfeeding-associated CMV infection acquisition. A cohort of 89 HIV-infected mothers and their children was studied. Women received antiretroviral therapy from week 25 of gestation until 6 months postpartum or indefinitely if meeting the criteria for treatment. All women were evaluated for CMV IgG presence and CMV DNA in breast milk. Children were tested for CMV infection by either the presence of IgM or the presence of CMV DNA in plasma at 1, 6 and 12 months and by the presence of IgG at 24 months. All mothers had high titers of CMV DNA in breast milk (5.7 log at Month 1 and 5.1 log at Month 6). Cumulative CMV infection rates were 60.3 % at Month 6, 69 % at Month 12 and 96.4 % at Month 24. There was a significant negative correlation between the duration of antiretroviral treatment during pregnancy and levels of CMV DNA in breast milk at Month 1 ( P = 0.033). There was a trend for a correlation between high titers of CMV DNA in breast milk at 6 months and CMV infection at 6 months ( P = 0.069). In this cohort, more than 95 % of the children had acquired CMV infection by 2 years of age. Besides breastfeeding, which played a major role, also horizontal transmission between 1 and 2 years was certainly relevant in determining CMV infection acquisition. [ABSTRACT FROM AUTHOR]

A 1-plane graph is a graph embedded in the plane such that each edge is crossed at most once. A 1-plane graph is optimal if it has maximum edge density. A red–blue edge coloring of an optimal 1-plane graph G partitions the edge set of G into blue edges and red edges such that no two blue edges cross each other and no two red edges cross each other. We prove the following: ( i ) Every optimal 1-plane graph has a red–blue edge coloring such that the blue subgraph is maximal planar while the red subgraph has vertex degree at most four; this bound on the vertex degree is worst-case optimal. ( ii ) A red–blue edge coloring may not always induce a red forest of bounded vertex degree. Applications of these results to graph augmentation and graph drawing are also discussed. [ABSTRACT FROM AUTHOR]

Purpose of the study The prevalence of frailty is expected to increase worldwide in parallel with demographic ageing. Despite this, little is known about the prevalence in different populations particularly community-based samples. This cross-sectional study evaluates the prevalence of frailty in a community-dwelling older adult population and describes a methodology to plan community-based interventions. Methodology A random sample of 1331 older adults, resident in the Lazio-Region of Italy, were screened by trained public health nurses (PHNs) by administering a validated questionnaire (the Functional Geriatric Evaluation questionnaire). Prevalence of frailty was calculated using the Final Synthetic Score derived from the questionnaire’s Final Score. Variables associated with frailty were selected through univariate and multivariate statistical analysis. Results Prevalence of frail (FS ≥ 10,≤50) and very frail (FS < 10) individuals was 13.9% and 7.6% respectively. Variables associated with frailty were age (older than 85 years), disability, living alone or the presence of a paid carer, lower education and neurological disorders like stroke, dementia, Parkinson disease and other neuropsychiatric diseases; Anaemia or cancer were also associated with a higher prevalence of frailty. Discussion The study provide a comprehensive picture of the prevalence of frailty and factors associated to this condition in community-dwelling older adults. On the basis of the study results, a plan of community-based services could address the needs of care of the elderly population. A trained team of PHNs may be the most appropriate personnel to carry out multidimensional frailty assessment in this setting. [ABSTRACT FROM AUTHOR]

Objectives: No data are available on bone metabolism in infants exposed to tenofovir during breastfeeding. We investigated bone metabolism markers in the first year of life in infants from mothers who received tenofovir, lamivudine and efavirenz during pregnancy and 12 months of breastfeeding in a national Option B+ programme in Malawi.Methods: Serum samples collected at 6 and 12 months in tenofovir-exposed infants and in a small sample of tenofovir-unexposed infants from the same clinical centre were analysed in batches for levels of bone-specific alkaline phosphatase (BAP; marker of bone formation) and of C-terminal telopeptide of type I collagen (CTX; marker of bone resorption).Results: Overall, 136 tenofovir-exposed infants were evaluated. No infant had at either timepoint CTX values above the upper normal limit, while most of them had at 6 and 12 months levels of BAP above the upper normal limit for the age range. Levels of bone markers showed no differences by gender and no association with growth parameters. Tenofovir-unexposed and -exposed children had similar mean levels of bone markers at 6 months (CTX: 0.62 versus 0.55 ng/mL, P = 0.122; BAP: 384 versus 362 U/L, P = 0.631).Conclusions: No significant association between treatment with tenofovir and CTX or BAP levels was found. The high levels of BAP, coupled to the normal levels observed for CTX, might reflect primarily skeletal growth. Potential negative effects of prolonged exposure to tenofovir through breastfeeding cannot however be excluded and longitudinal studies that evaluate bone mineralization status in children enrolled in Option B+ programmes are warranted. [ABSTRACT FROM AUTHOR]

Let 〈 G r , G b 〉 be a pair of plane st -graphs with the same vertex set V . A simultaneous visibility representation with L-shapes of 〈 G r , G b 〉 is a pair of bar visibility representations 〈 Γ r , Γ b 〉 such that, for every vertex v ∈ V , Γ r ( v ) and Γ b ( v ) are a horizontal and a vertical segment, respectively, which share an end-point. In other words, every vertex is drawn as an L-shape, every edge of G r is a vertical visibility segment, and every edge of G b is a horizontal visibility segment. Also, no two L-shapes intersect each other. An L-shape has four possible rotations, and we assume that each vertex is given a rotation for its L-shape as part of the input. Our main results are: (i) a characterization of those pairs of plane st -graphs admitting such a representation, (ii) a quadratic time algorithm to recognize them, and (iii) a linear time drawing algorithm if the test is positive. As an application, starting from a simultaneous visibility representation with L-shapes, we show how to compute a simultaneous embedding of the two graphs with at most two bends per edge and right-angle crossings. [ABSTRACT FROM AUTHOR]

Let G be a 3-connected planar graph with n vertices and let p ( G ) be the maximum number of vertices of an induced subgraph of G that is a path. Substantially improving previous results, we prove that p ( G ) ≥ log ⁡ n 12 log ⁡ log ⁡ n . To demonstrate the tightness of this bound, we notice that the above inequality implies p ( G ) ∈ Ω ( ( log 2 ⁡ n ) 1 − ε ) , where ε is any positive constant smaller than 1, and describe an infinite family of planar graphs for which p ( G ) ∈ O ( log ⁡ n ) . As a byproduct of our research, we prove a result of independent interest: Every 3-connected planar graph with n vertices contains an induced subgraph that is outerplanar and connected and that contains at least n 3 vertices. The proofs in the paper are constructive and give rise to O ( n ) -time algorithms. [ABSTRACT FROM AUTHOR]

Let ε, ε be two non negative numbers. An approximate rectangle of influence drawing (also called ( ε, ε)-RID) is a proximity drawing of a graph such that: (i) if u, v are adjacent vertices then their rectangle of influence 'scaled down' by the factor $\frac{1}{1+\varepsilon_{1}}$ does not contain other vertices of the drawing; (ii) if u, v are not adjacent, then their rectangle of influence 'blown-up' by the factor 1+ ε contains some vertices of the drawing other than u and v. Firstly, we prove that all planar graphs have an ( ε, ε)-RID for any ε>0 and ε>0, while there exist planar graphs which do not admit an ( ε,0)-RID and planar graphs which do not admit a (0, ε)-RID. Then, we investigate (0, ε)-RIDs; we prove that both the outerplanar graphs and a suitably defined family of graphs without separating 3-cycles admit this type of drawing. Finally, we study polynomial area approximate rectangle of influence drawings and prove that (0, ε)-RIDs of proper track planar graphs (a superclass of the outerplanar graphs) can be computed in polynomial area for any ε>2. As for values of ε such that ε≤2, we describe a drawing algorithm that computes (0, ε)-RIDs of binary trees in area $O(n^{c + f(\varepsilon_{2})})$, where c is a positive constant, f( ε) is a poly-logarithmic function that tends to infinity as ε tends to zero, and n is the number of vertices of the input tree. [ABSTRACT FROM AUTHOR]

Abstract: Objective: We present a new software system, VisFAN, for the visual analysis of financial activity networks. Methods: We combine enhanced graph drawing techniques to devise novel algorithms and interaction functionalities for the visual exploration of networked data sets, together with tools for SNA and for the automatic generation of reports. Results: An application example constructed on real data is presented. We also report the results of a study aimed at qualitatively understanding the satisfaction level of the analysts when using VisFAN. Conclusion: VisFAN makes a strong use of visual interactive tools, combined with ad-hoc clustering techniques and customizable layout constraints management. Implications: As this system confirms, information visualization can play a crucial role to face the discovery of financial crimes. [Copyright &y& Elsevier]

It is proved that every series-parallel digraph whose maximum vertex degree is Δ admits an upward planar drawing with at most one bend per edge such that each edge segment has one of Δ distinct slopes. The construction is worst-case optimal in terms of the number of slopes, and it gives rise to drawings with optimal angular resolution π Δ. A variant of the drawing algorithm is used to show that (non-directed) reduced series-parallel graphs and flat series-parallel graphs have a (non-upward) 1-bend planar drawing with ⌈ Δ 2 ⌉ distinct slopes if biconnected, and with ⌈ Δ 2 ⌉ + 1 distinct slopes if connected. [ABSTRACT FROM AUTHOR]

• For n ≥ 14 there is a properly 2-colored SP-graph with 2 n + 4 vertices s.t. any 2-colored PSE requires Ω (n) bends on Ω (n) edges • 2 bends per edge suffice for a 2-colored PSE of properly 2-colored outerplanar graphs • 1 bend per edge suffices for a 2-colored PSE of a properly 2-colored outerplanar graph if the points are linearly separable • 3 bends per edge suffice for a 2-colored PSE of a 2-colored outerplanar graph • 1 bend per edge suffices for a 2-colored PSE of a 2-colored caterpillar Let G be a planar graph whose vertices are colored either red or blue and let S be a set of points having as many red (resp. blue) points as the red (resp. blue) vertices of G. A 2-colored point-set embedding of G on S is a planar drawing that maps each red (resp. blue) vertex of G to a red (resp. blue) point of S. We show that there exist partial 2-trees that are properly 2-colored (i.e., they are 2-colored with no two adjacent vertices have the same color), whose point-set embeddings may require linearly many bends on linearly many edges. For a contrast, we show that two bends per edge are sufficient for 2-colored point-set embedding of properly 2-colored outerplanar graphs. For separable point sets this bound reduces to one, which is worst-case optimal. If the 2-coloring of the outerplanar graph is not proper, three bends per edge are sufficient and one bend per edge (which is worst-case optimal) is sufficient for caterpillars. [ABSTRACT FROM AUTHOR]

We present a new model for hybrid planarity that relaxes existing hybrid representation models. A graph G = (V , E) is (k , p) -planar if V can be partitioned into clusters of size at most k such that G admits a drawing where: (i) each cluster is associated with a closed, bounded planar region, called a cluster region ; (ii) cluster regions are pairwise disjoint, (iii) each vertex v ∈ V is identified with at most p distinct points, called ports , on the boundary of its cluster region; (iv) each inter-cluster edge (u , v) ∈ E is identified with a Jordan arc connecting a port of u to a port of v ; (v) inter-cluster edges do not cross or intersect cluster regions except at their end-points. We first tightly bound the number of edges in a (k , p) -planar graph with p < k. We then prove that (4 , 1) -planarity testing and (2 , 2) -planarity testing are NP-complete problems. Finally, we prove that neither the class of (2 , 2) -planar graphs nor the class of 1-planar graphs contains the other, indicating that the (k , p) -planar graphs are a large and novel class. [ABSTRACT FROM AUTHOR]

Background: In sub-Saharan African countries Epstein Barr virus (EBV) infection occurs in early childhood. We aim to investigate the factors associated with EBV acquisition and the impact of EBV infection on the humoral response to HBV vaccination in infants born from HIV-positive, antiretroviral-treated mothers in Malawi. Methods: A total of 149 HIV-exposed infants were included in this longitudinal study. EBV anti-VCA IgG were measured using an ELISA assay. The EBV seroconversion was correlated with the maternal viro-immunological conditions, with infant growth and immunological vulnerability, and with the humoral response to the HBV vaccine. Results: No infant was EBV-positive at 6 months (n. 52 tested). More than a third of infants (49/115 or 42.6 %) on study beyond 6 months seroconverted at 12 months. At 24 months, out of 66 tested infants, only 13 remained EBV-uninfected, while 53 (80.3 %) acquired EBV infection, rising the total proportion of EBV seroconversion to 88.7 % (102/115 infants). EBV seroconversion was significantly associated with a low maternal educational status but had no impact on infant growth or vulnerability to infections. Reduced HBsAb levels and accelerated waning of antibodies were associated with early EBV seroconversion. Conclusions: We found a heterogeneous timing of acquisition of EBV with the majority of infants born from HIV + mothers acquiring infection after 6 months. Anti-HBs levels were lower and appeared to wane faster in infants acquiring EBV infection. [ABSTRACT FROM AUTHOR]

The edge-length ratio of a planar straight-line drawing of a graph is the maximum ratio between the lengths of any two of its edges. When the edges to be considered in the ratio are required to be adjacent, the ratio is called local edge-length ratio. The (local) edge-length ratio of a graph G is the infimum over all (local) edge-length ratios in the planar straight-line drawings of G. We prove that the edge-length ratio of the n -vertex 2-trees is Ω (log n) , which proves a conjecture by Lazard et al. [TCS 770, 2019, pp. 88–94] and complements an upper bound by Borrazzo and Frati [JoCG 11(1), 2020, pp. 137–155]. We also prove that every partial 2-tree admits a planar straight-line drawing whose local edge-length ratio is at most 4 + for any arbitrarily small > 0. [ABSTRACT FROM AUTHOR]

This paper studies a packing problem in the so-called beyond-planar setting, that is when the host graph is "almost-planar" in some sense. Precisely, we consider the case that the host graph is k -planar, i.e., it admits an embedding with at most k crossings per edge, and focus on families of Δ -regular caterpillars, that are caterpillars whose non-leaf vertices have the same degree Δ. We study the dependency of k from the number h of caterpillars that are packed, both in the case that these caterpillars are all isomorphic to one another (in which case the packing is called placement) and when they are not. We give necessary and sufficient conditions for the placement of h Δ -regular caterpillars and sufficient conditions for the packing of a set of Δ 1 -, Δ 2 -, ... , Δ h -regular caterpillars such that the degree Δ i and the degree Δ j of the non-leaf vertices can differ from one caterpillar to another, for 1 ≤ i , j ≤ h , i ≠ j. [ABSTRACT FROM AUTHOR]

We establish new results on the curve complexity of k -colored point-set embeddings when k = 3. We show that there exist 3-colored caterpillars with only three independent edges whose 3-colored point-set embeddings may require Ω (n 1 3 ) bends on Ω (n 2 3 ) edges. This settles an open problem by Badent et al. [5] about the curve complexity of point set embeddings of k -colored trees and it extends a lower bound by Pach and Wenger [35] to the case that the graph only has O (1) independent edges. Concerning upper bounds, we prove that any 3-colored path admits a 3-colored point-set embedding with curve complexity at most 4. In addition, we introduce a variant of the k -colored simultaneous embeddability problem and study its relationship with the k -colored point-set embeddability problem. [ABSTRACT FROM AUTHOR]

We study the problem of representing topological graphs as polyline drawings with few bends per edge and such that the topology of the graph is either fully or partially preserved. More formally, let G be a simple topological graph and let Γ be a polyline drawing of G. Drawing Γ partially preserves the topology of G if it has the same external boundary, the same circular order of the edges around each vertex, and the same set of crossings as G , while it fully preserves the topology of G if the planarization of G and the planarization of Γ have the same planar embedding. We prove that if the set of crossing-free edges of G forms a biconnected (connected) spanning subgraph, then G admits a polyline drawing that partially preserves its topology and that has curve complexity at most one (three), i.e., with at most one (three) bend(s) per edge. If, however, the set of crossing-free edges of G is not a connected spanning subgraph, the curve complexity may be Ω (n) , while it is O (1) if the number of connected components is O (1). Concerning drawings that fully preserve the topology, we show that if G is k -skew (i.e., it becomes planar after removing k suitably chosen edges), it admits one such drawing with curve complexity at most 2 k ; for 1-skew graphs, the curve complexity can be reduced to one, which is a tight bound. We also consider optimal 2-plane graphs (i.e., with at most two crossings per edge and maximum edge density), for which we discuss trade-offs between curve complexity and crossing angle resolution of drawings that fully preserve the topology. [ABSTRACT FROM AUTHOR]

Background: HIV-exposed uninfected (HEU) infants show a high rate of morbidity. We aimed to investigate on biomarkers of immune activation/microbial translocation in HEU infants, evaluating the impact that infections/malnutrition can have on biomarker levels during the first year of life.Methods: Clinical data of 72 Malawian infants were recorded monthly and correlated with levels of soluble CD14 (sCD14), lipopolysaccharide-binding protein (LBP) and intestinal fatty acid-binding protein (I-FABP), analyzed longitudinally.Results: Levels of sCD14 and LBP showed a significant age-related increase. Higher levels of LBP (19.4 vs. 15.2 μg/ml) were associated with stunting, affecting 30% of the infants. The association remained statistically significant after adjusting for cytomegalovirus acquisition, malaria and respiratory infections (p = 0.031). I-FABP levels were significantly increased in infants experiencing gastrointestinal infections (1442.8 vs. 860.0 pg/ml, p = 0.018).Conclusion: We provide evidence that stunting is associated with an enhanced inflammatory response to microbial products in HEU children, suggesting that malnutrition status should be taken into consideration to better understand the alteration of the immune profile of HEU infants living in poor socioeconomic settings. [ABSTRACT FROM AUTHOR]

• Hypergammaglobulinemia is common in Malawian HIV-positive pregnant women. • Twenty-four months of antiretroviral therapy improved but did not normalize IgG anomalies. • The IgG2 isotype remained highly underrepresented. • The potential influence of immunoglobulin disorders should be considered when assessing the risk of infection in HIV-exposed infants. Hypergammaglobulinemia and anomalies in the IgG subclass distribution are common in HIV-infected individuals and persist even after many years of antiretroviral therapy (ART). The aim of this study was to investigate the IgG profile and dynamics in pregnant HIV-infected Malawian women in the Option B era. Thirty-seven treatment-naive women received ART from the third trimester of pregnancy to 6 months post delivery (end of the breastfeeding period). ART continuation (group C) or interruption (group I) was then decided on the basis of the CD4+ cell count at enrolment (>350 or ≤350/μl). Total IgG and IgG subclasses were determined in maternal serum using a nephelometric assay at baseline and at 6 and 24 months postpartum. At enrolment, 36/37 women had IgG levels >15 g/l and there was a predominance of the IgG1 isotype (more than 90%) in parallel with underrepresentation of IgG2 (5.0%). After 6 months of ART, both groups showed a significant median decrease in total IgG (−3.1 g/l in group I, −3.5 g/l in group C) and in IgG1 (−4.0 g/l and −3.6 g/l, respectively), but only a modest recovery in IgG2 levels (+0.16 in group I, +0.14 g/l in group C). At month 24, hypergammaglobulinemia was still present in 73.7% of women in group C, although a significant reduction was observed in total IgG level and in IgG1 and IgG3 subclasses (p < 0.0001 in all cases). IgG2 levels did not show any significant change. In group I at 24 months, total IgG and IgG subclasses had returned to levels comparable to those at baseline. The beneficial effects of 24 months of ART appear to be limited in the B-cell compartment, with an incomplete reduction of total IgG levels and no recovery of IgG2 depletion. A short ART period did not have significant effects on IgG abnormalities in women who interrupted treatment. [ABSTRACT FROM AUTHOR]

We prove that every set of Δ - 1 slopes is 1-bend universal for the planar graphs with maximum vertex degree Δ . This means that any planar graph with maximum degree Δ admits a planar drawing with at most one bend per edge and such that the slopes of the segments forming the edges can be chosen in any given set of Δ - 1 slopes. Our result improves over previous literature in three ways: Firstly, it improves the known upper bound of 3 2 (Δ - 1) on the 1-bend planar slope number; secondly, the previously known algorithms compute 1-bend planar drawings by using sets of O (Δ) slopes that may vary depending on the input graph; thirdly, while these algorithms typically minimize the slopes at the expenses of constructing drawings with poor angular resolution, we can compute drawings whose angular resolution is at least π Δ - 1 , which is worst-case optimal up to a factor of 3 4 . Our proofs are constructive and give rise to a linear-time drawing algorithm. [ABSTRACT FROM AUTHOR]

Abstract We show that any outerplanar graph admits a planar straight-line drawing such that the length ratio of the longest to the shortest edges is strictly less than 2. This result is tight in the sense that for any ϵ > 0 there are outerplanar graphs that cannot be drawn with an edge-length ratio smaller than 2 − ϵ. We also show that this ratio cannot be bounded if the embeddings of the outerplanar graphs are given. [ABSTRACT FROM AUTHOR]

The use of graph visualization approaches to present and analyze complex data is taking a leading role in conveying information and knowledge to users in many application domains. This creates the need of developing efficient and effective algorithms that automatically compute graph layouts. In this respect, force-directed algorithms are arguably among the most popular graph layout techniques. Aimed at leveraging the potential of modern distributed graph algorithms platforms, we present Multi-GiLA, the first multilevel force-directed graph visualization algorithm based on a vertex-centric computation paradigm. We implemented Multi-GiLA using the Apache Giraph platform. Experiments show that it can be successfully applied to compute high quality layouts of very large graphs on inexpensive cloud computing platforms. [ABSTRACT FROM AUTHOR]

Background: Transplacental passage of IgGs is impaired in HIV + pregnant women, possibly determining an inadequate immunological protection in their children. We aimed to determine the impact of maternal immunological IgG profile and immunoactivation status on the efficiency of transplacental passage of IgG subclasses in HIV + mothers.Methods: 16 mother/infants pairs were studied in Malawi. Mothers received antiretroviral therapy (ART) from the third trimester of pregnancy. Determinations of pre-ART levels of maternal sCD14, of IgG subclasses in mothers at delivery and in their 1-month-old infants, were performed using commercial ELISA kits.Results: At delivery, after a median of 10 weeks of ART, 12/16 mothers were hypergammaglobulinemic, with IgG levels (20.5 mg/ml, 95% CI:18.8-26.8) directly correlated to the plasmatic levels of sCD14 (r = 0.640, p = 0.014). IgG1 levels (17.9 mg/ml) accounted for 82% of IgG, IgG3 and IgG4 levels were in the normal range. A profound deficit of IgG2 was observed both in mothers (0.60 mg/ml) and in infants (0.14 mg/ml). Placental transfer ratio (range 0.16-0.42) did not show a selective impairment between the different IgG subclasses. The transplacental passage of all IgG subclasses was decreased in the presence of maternal IgG over 16 mg/ml (significantly for IgG1, p = 0.031) and of high levels of sCD14 (p = 0.063).Conclusions: Transplacental passage was reduced for all IgG subclasses and inversely correlated to high levels of maternal IgGs and to the degree of immunoactivation. The profound depression of IgG2 in mothers suggests that IgG2 neonatal levels mostly reflect the maternal deficit rather than a selective impairment of IgG2 transfer. [ABSTRACT FROM AUTHOR]

The prevalence of non-communicable diseases has risen sharply in recent years, particularly among older individuals who require complex drug regimens. Patients are increasingly required to manage their health through medication adherence and self-care, but about 50% of patients struggle to adhere to prescribed treatments. This study explored the relationship between interest in medication adherence, health literacy, and self-care and how it changed during the COVID-19 pandemic. We used Google Trends to measure relative search volumes (RSVs) for these three topics from 2012 to 2022. We found that interest in self-care increased the most over time, followed by health literacy and medication adherence. Direct correlations emerged between RSVs for medication adherence and health literacy (r = 0.674, p < 0.0001), medication adherence and self-care (r = 0.466, p < 0.0001), and health literacy and self-care (r = 0.545, p < 0.0001). After the COVID-19 pandemic outbreak, interest in self-care significantly increased, and Latin countries showed a greater interest in self-care than other geographical areas. This study suggests that people are increasingly interested in managing their health, especially in the context of the recent pandemic, and that infodemiology may provide interesting information about the attitudes of the population toward chronic disease management. [ABSTRACT FROM AUTHOR]

Abstract: Problem: Data on soluble CD14 (sCD14) during pregnancy and lactation are scarce. We assessed the levels of sCD14 in plasma and breastmilk of Malawian HIV‐positive women and evaluated the possible association with morbidity and mortality in the HIV‐exposed children. Method of study: One hundred and forty‐nine mother/child pairs were studied. Women received antiretroviral therapy from 26 weeks of gestation to at least 6 months of exclusive breastfeeding. sCD14 concentrations were determined using an enzyme‐linked immunosorbent assay. Results: sCD14 levels measured at 26 weeks of pregnancy (median: 1418 ng/mL, IQR: 1086‐1757) were inversely correlated to maternal CD4+ cell count (r = −.283, P = .001) and to neonatal birthweight (r = −.233, P = .008). At 6 months, sCD14 plasma levels were significantly higher compared to baseline (1993 ng/mL, IQR: 1482‐2604, P < .001), and breastmilk sCD14 levels (7668 ng/mL, IQR: 5495‐10207) were 4‐fold higher than in plasma (although the concentrations in the two compartments were not correlated). No association was found between sCD14 levels in plasma or breastmilk and morbidity or mortality in children. Conclusion: Higher sCD14 levels in HIV‐positive women were associated with a more compromised maternal immunological status and to a lower neonatal birthweight, but not to poorer clinical outcomes in the HIV‐exposed children. [ABSTRACT FROM AUTHOR]

The article discusses research that examined the association of hepatitis E virus (HEV) prevalence with HIV infection in sub-Saharan Africa, focusing on pregnant Malawian women. Topics covered include the seroprevalence of hepatitis E during pregnancy, the rate of new HEV infections 2 years after delivery, and HEV prevalence in HIV-exposed children in the endemic area.

A drawing of a graph is 1-planar if each edge is crossed at most once. A graph is 1-planar if it has a 1-planar drawing. A k-bend RAC (Right Angle Crossing) drawing of a graph is a polyline drawing where each edge has at most k bends and edges cross only at right angles. A graph is k-bend RAC if it has a k -bend RAC drawing. A 0-bend RAC graph (drawing) is also called a straight-line RAC graph (drawing) . The relationships between 1-planar and k -bend RAC graphs have been partially studied in the literature. It is known that there are both 1-planar graphs that are not straight-line RAC and straight-line RAC graphs that are not 1-planar. The existence of 1-planar straight-line RAC drawings has been proven only for restricted families of 1-planar graphs. Two of the main questions still open are: ( i ) What is the complexity of deciding whether a graph has a drawing that is both 1-planar and straight-line RAC? ( i i ) Does every 1-planar graph have a drawing that is both 1-planar and 1-bend RAC? In this paper we answer these two questions. Namely, we prove an NP-hardness result for the first question, and we positively answer the second question by describing a drawing algorithm for 1-planar graphs. [ABSTRACT FROM AUTHOR]

We study the problem of computing drawings of planar graphs in sub-quadratic area, by allowing edge crossings. We first prove that sub-quadratic area cannot be achieved if only a constant number of crossings per edge is allowed. More precisely, we show that the same area lower bounds as in the crossing-free case hold for straight-line and poly-line drawings of planar graphs and seriesparallel graphs. Motivated by this result, we study straight-line drawings of planar graphs where the number of crossings per edge is not bounded by a constant. In this case, we prove that every planar graph admits a straight-line drawing with sub-quadratic area and sub-linear thickness (the thickness of a drawing is the minimum number of colors that can be assigned to the edges so that each color class induces a planar drawing). We also prove that every partial 2-tree (and hence every series-parallel graph) admits a linear-area straight-line drawing with thickness at most 10. It is worth remarking that a drawing with thickness h - 1 is h-quasi planar, i.e. it does not contain h-mutually crossing edges. The main ingredient to prove our results is (c, t)-track layouts, a combinatorial tool that can be represented as a drawing where: (i) each vertex is assigned to one of t horizontal layers (tracks), (ii) no two adjacent vertices are on the same track, (iii) each edge receives one of c colors, so that no two edges of the same color (u, v) and (w, z) cross if u, w are on the same track, and v, z are on the same track. [ABSTRACT FROM AUTHOR]

We study universal sets of slopes for computing upward planar drawings of planar st-graphs. We first consider a subfamily of planar st-graphs, called bitonic st-graphs. We prove that every set S of Δ slopes containing the horizontal slope is universal for 1-bend upward planar drawings of bitonic st-graphs with maximum vertex degree Δ , i.e., every such digraph admits a 1-bend upward planar drawing whose edge segments use only slopes in S . This result is worst-case optimal in terms of number of slopes, and, for a suitable choice of S , it gives rise to drawings with worst-case optimal angular resolution. We then prove that every such set S can be used to construct 2-bend upward planar drawings of n-vertex planar st-graphs with at most 4 n - 9 bends in total. [ABSTRACT FROM AUTHOR]

A simultaneous geometric embedding (SGE) of two planar graphs G1 and G2 with the same vertex set is a pair of straight-line planar drawings Γ1 of G1 and Γ2 of G2 such that each vertex is drawn at the same point in Γ1 Γ2. Many papers have been devoted to the study of which pairs of graphs admit a SGE, and both positive and negative results have been proved. We extend the study of SGE, by introducing and characterizing a new class of planar graphs that makes it possible to immediately extend several positive results that rely on the property of strictly monotone paths. Moreover, we introduce a relaxation of the SGE setting where Γ1 and Γ2 are required to be quasi-planar (i.e. they can have crossings provided that there are no three mutually crossing edges). This relaxation allows for the simultaneous embedding of pairs of planar graphs that are not simultaneously embeddable in the classical SGE setting and opens up several new interesting research questions. [ABSTRACT FROM AUTHOR]

The planar slope numberpsn(G)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${{\,\textrm{psn}\,}}(G)$$\end{document} of a planar graph G is the minimum number of edge slopes in a planar straight-line drawing of G. It is known that psn(G)∈O(cΔ)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${{\,\textrm{psn}\,}}(G) \in O(c^{\Delta })$$\end{document} for every planar graph G of maximum degree Δ\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\Delta $$\end{document}. This upper bound has been improved to O(Δ5)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(\Delta ^5)$$\end{document} if G has treewidth three, and to O(Δ)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(\Delta )$$\end{document} if G has treewidth two. In this paper we prove psn(G)≤max{4,Δ}\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${{\,\textrm{psn}\,}}(G) \le \max \{4,\Delta \}$$\end{document} when G is a Halin graph, and thus has treewidth three. Furthermore, we present the first polynomial upper bound on the planar slope number for a family of graphs having treewidth four. Namely we show that O(Δ2)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(\Delta ^2)$$\end{document} slopes suffice for nested pseudotrees. [ABSTRACT FROM AUTHOR]

Background Virtually all HIV-infected women in sub-Saharan Africa have evidence of Cytomegalovirus (CMV) infection and levels of specific anti-CMV IgG have been suggested to represent more intense reactivation of subclinical infection. Studies have also shown direct influence of CMV on lymphocytes. Objective The aim of this study was to determine if levels of anti-CMV specific antibodies could impact on the immunological response to antiretroviral treatment (ART) in HIV-infected pregnant women. Study design CMV-specific IgG were measured in HIV-infected pregnant women at 26 weeks of gestation (before ART initiation). Women received ART until 6 months postpartum or indefinitely according to local guidelines at the time of the study. Immunological and virological responses were assessed 6 months and 24 months after delivery. Results A total of 81 women were studied. At baseline high levels (above the median) of specific IgG were associated to a low CD4+ cell count (P< 0.001), a high viral load (P = 0.003), and to an older age (P = 0.051). In a multivariate model adjusting for baseline CD4+ count, baseline viral load and age, the presence of low levels of CMV IgG was the only independent predictor of a a CD4+ count above 500/mm 3 24 months after delivery among women on continuous therapy. Conclusions In this cohort, levels of CVM IgG had a significant influence on the immunological response to ART, adding information to the known impact of CMV infection in the HIV-positive population, and underlining the need of new strategies to contain the infection. [ABSTRACT FROM AUTHOR]

Abstract: We propose an approach that allows a user (e.g., an analyst) to explore a layout produced by any graph drawing algorithm, in order to reduce the visual complexity and clarify its presentation. Our approach is based on stratifying the drawing into layers with desired properties; to this aim, heuristics are presented. The produced layers can be explored and combined by the user to gradually acquire details. We present a user study to test the effectiveness of our approach. Furthermore, we performed an experimental analysis on popular force-directed graph drawing algorithms, in order to evaluate what is the algorithm that produces the smallest number of layers and if there is any correlation between the number of crossings and the number of layers of a graph layout. The proposed approach is useful to explore graph layouts, as confirmed by the presented user study. Furthermore, interesting considerations arise from the experimental evaluation, in particular, our results suggest that the number of layers of a graph layout may represent a reliable measure of its visual complexity. The algorithms presented in this paper can be effectively applied to graph layouts with a few hundreds of edges and vertices. For larger drawings that contain lots of crossings, the time complexity of our algorithms grows quadratically in the number of edges and more efficient techniques need to be devised. The proposed approach takes as input a layout produced by any graph drawing algorithm, therefore it can be applied in a variety of application domains. Several research directions can be explored to extend our framework and to devise new visualization paradigms to effectively present stratified drawings. [Copyright &y& Elsevier]