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]

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]

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]

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 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 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]

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]

Background: HIV infection is a major contributor to maternal mortality in resource-limited settings. The Drug Resource Enhancement Against AIDS and Malnutrition Programme has been promoting HAART use during pregnancy and postpartum for Prevention-of-mother-to-child-HIV transmission (PMTCT) irrespective of maternal CD4 cell counts since 2002. Methods: Records for all HIV+ pregnancies followed in Mozambique and Malawi from 6/2002 to 6/2010 were reviewed. The cohort was comprised by pregnancies where women were referred for PMTCT and started HAART during prenatal care (n = 8172, group 1) and pregnancies where women were referred on established HAART (n = 1978, group 2). Results: 10,150 pregnancies were followed. Median (IQR) baseline values were age 26 years (IQR:23–30), CD4 count 392 cells/mm3 (IQR:258–563), Viral Load log10 3.9 (IQR:3.2–4.4), BMI 23.4 (IQR:21.5–25.7), Hemoglobin 10.0 (IQR: 9.0–11.0). 101 maternal deaths (0.99%) occurred during pregnancy to 6 weeks postpartum: 87 (1.1%) in group 1 and 14 (0.7%) in group 2. Mortality was 1.3% in women with

Abstract: A Right Angle Crossing Graph (also called a RAC graph for short) is a graph that has a straight-line drawing where any two crossing edges are orthogonal to each other. A -planar graph is a graph that has a drawing where every edge is crossed at most once. This paper studies the combinatorial relationship between the family of RAC graphs and the family of -planar graphs. It is proved that: (1) all RAC graphs having maximal edge density belong to the intersection of the two families; and (2) there is no inclusion relationship between the two families. As a by-product of the proof technique, it is also shown that every RAC graph with maximal edge density is the union of two maximal planar graphs. [Copyright &y& Elsevier]

Abstract: This paper studies the problem of drawing directed acyclic graphs in three dimensions in the straight-line grid model so that all directed edges are oriented in a common (upward) direction. We show that there exists a family of outerplanar directed acyclic graphs whose volume requirement is super-linear. We also prove that for the case of directed trees a linear-volume upper bound is achievable. [Copyright &y& Elsevier]

Abstract: This paper investigates the basic problem of computing crossing-free straight-line 3D grid drawings of graphs such that the overall volume is small. Motivated by their relevance in the literature, we focus on families of graphs having constant queue number and on k-trees. We present algorithms that compute drawings of these families of graphs on 3D grids consisting of a constant number of parallel lines and such that the overall volume is linear. Lower bounds on the number of such grid lines are also provided. Our results extend and improve similar ones already described in the literature. [Copyright &y& Elsevier]

Given a set of n points in the plane, any β-skeleton and [γ0,γ1]-graph can be computed in quadratic time. The presented algorithms are optimal for β values that are less than 1 and [γ0,γ1] values that result in non-planar graphs. We show a numerically robust algorithm that computes Gabriel graphs in quadratic time and degree 2. We finally show how a β-spectrum can be computed in optimal O(n2) time. [Copyright &y& Elsevier]

We study the problem of characterizing sets of points whose Voronoi diagrams are trees and if so, what are the combinatorial properties of these trees. The second part of the problem can be naturally turned into the following graph drawing question: Given a tree T, can one represent T so that the resulting drawing is a Voronoi diagram of some set of points? We investigate the problem both in the Euclidean and in the Manhattan metric. The major contributions of this paper are as follows.

We determine the reachability properties of the embeddings in R3 of a directed path, in the graph-theoretic sense, whose edges have each been assigned a desired direction (East, West, North, South, Up, or Down) but no length. We ask which points of R3 can be reached by the terminus of an embedding of such a path, by choosing appropriate positive lengths for the edges, if the embedded path starts at the origin, does not intersect itself, and respects the directions pre-assigned to its edges. This problem arises in the context of extending planar graph embedding techniques and VLSI rectilinear layout techniques from 2D to 3D. We give a combinatorial characterization of reachability that yields linear time recognition and layout algorithms. Finally, we extend our characterization to Rd, d>3. [Copyright &y& Elsevier]

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]

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]

• 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]

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]

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]

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]

Background Coinfection with the hepatitis viruses is common in the HIV population in sub-Saharan Africa. The aim of this study was to assess, in a cohort of HIV-infected pregnant women receiving antiretroviral drugs (ARVs), the prevalence of HBV and HCV infections and to determine the impact of these infections on the occurrence of liver toxicity and on the viroimmunological response. Methods Women were screened for HBsAg and HCV-RNA before starting, at week 25 of gestational age, an antiretroviral regimen consisting of lamivudine and nevirapine plus either stavudine or zidovudine. Women with CD4+ < 350/mm³ continued ARVs indefinitely, while the other women interrupted treatment 6 months postpartum (end of breastfeeding period). Both groups were followed for 2 years after delivery. Liver function was monitored by alanine aminotransferase (ALT) measurement. The Cox proportional hazards model was used to identify factors associated with the emergence of liver toxicity. Results A total of 28 women out of the 309 enrolled in the study (9.1%) were coinfected with HBV (n. 27), or HCV (n. 1). During follow-up 125 women (40.4%) developed a grade ⩾ 1 ALT elevation, 28 (9.1%) a grade ⩾ 2 and 6 (1.9%) an elevation defining grade 3 toxicity. In a multivariate model including age, baseline CD4+ count and hemoglobin level, the presence of either HBV or HCV infection was significantly associated with the development of an ALT increase of any grade (P = 0.035). Moderate or severe liver laboratory toxicity (grade ⩾ 2) was more frequent among women with baseline CD4+ > 250/mm³ (P = 0.030). In HBVinfected women a baseline HBV-DNA level above 10,000 IU/ml was significantly associated to the development of liver toxicity of grade ⩾ 1 (P = 0.040). Coinfections had no impact on the immunological and virological response to antiretroviral drugs up to 2 years after delivery. Conclusions In this cohort of nevirapine-treated women the presence of HBV or HCV was associated only to the development of mild liver toxicity, while the occurrence of moderate or severe hepatoxicity was correlated to a baseline CD4+ count > 250/mm³. No statistically significant effect of the coinfections was observed on the efficacy of antiretroviral therapy. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we study how to compute compact straight-line drawings of planar graphs with a limited number of crossings per edge. We prove that every outerplanar graph can be drawn in area using a sub-linear number of crossings per edge, and that for any given number , every outerplanar graph admits an area drawing with crossing per edge. The drawing algorithms run in linear time and can be also generalized to another meaningful sub-family of series–parallel graphs with bounded vertex-degree. [Copyright &y& Elsevier]

We study the problem of representing a graph as a storyplan, a recently introduced model for dynamic graph visualization. It is based on a sequence of frames, each showing a subset of vertices and a planar drawing of their induced subgraphs, where vertices appear and disappear over time. Namely, in the StoryPlan problem, we are given a graph and we want to decide whether there exists a total vertex appearance order for which a storyplan exists. We prove that the problem is NP -complete, and complement this hardness with two parameterized algorithms, one in the vertex cover number and one in the feedback edge set number of the input graph. We prove that partial 3-trees always admit a storyplan, which can be computed in linear time. Finally, we show that the problem remains NP -complete if the vertex appearance order is given and we have to choose how to draw the frames. [ABSTRACT FROM AUTHOR]

Abstract: We introduce and study -EMST drawings, i.e., planar straight-line drawings of trees such that, for any fixed , the distance between any two vertices is at least the length of the longest edge in the path connecting them. -EMST drawings are good approximations of Euclidean minimum spanning trees. While it is known that only trees with bounded degree have a Euclidean minimum spanning tree realization, we show that every tree T has a -EMST drawing for any given . We also present drawing algorithms that compute -EMST drawings of trees with bounded degree in polynomial area. As a byproduct of one of our techniques, we improve the best known area upper bound for Euclidean minimum spanning tree realizations of complete binary trees. [Copyright &y& Elsevier]

Abstract: Cognitive experiments show that humans can read graph drawings in which all edge crossings are at right angles equally well as they can read planar drawings; they also show that the readability of a drawing is heavily affected by the number of bends along the edges. A graph visualization whose edges can only cross perpendicularly is called a RAC (Right Angle Crossing) drawing. This paper initiates the study of combinatorial and algorithmic questions related to the problem of computing RAC drawings with few bends per edge. Namely, we study the interplay between number of bends per edge and total number of edges in RAC drawings. We establish upper and lower bounds on these quantities by considering two classical graph drawing scenarios: The one where the algorithm can choose the combinatorial embedding of the input graph and the one where this embedding is fixed. [Copyright &y& Elsevier]

Abstract: The contribution of this paper is twofold. It presents a new approach to the matched drawability problem of pairs of planar graphs and it provides four algorithms based on this approach for drawing the pairs , , and . Further, it initiates the study of the matched drawability of triples of planar graphs: it presents an algorithm to compute a matched drawing of a triple of cycles and an algorithm to compute a matched drawing of a caterpillar and two unlabeled level planar graphs. The results extend previous work on the subject and relate to existing literature about simultaneous embeddability and unlabeled level planarity. [Copyright &y& Elsevier]

Abstract: Given a graph G with n vertices and a set S of n points in the plane, a point-set embedding of G on S is a planar drawing such that each vertex of G is mapped to a distinct point of S. A geometric point-set embedding is a point-set embedding with no edge bends. This paper studies the following problem: The input is a set S of n points, a planar graph G with n vertices, and a geometric point-set embedding of a subgraph on a subset of S. The desired output is a point-set embedding of G on S that includes the given partial drawing of . We concentrate on trees and show how to compute the output in time in a real-RAM model and with at most edges with at most bends, where k is the number of vertices of the given subdrawing. We also prove that there are instances of the problem which require at least bends on edges. [Copyright &y& Elsevier]

Abstract: Let be a planar graph with vertices and with a partition of the vertex set into subsets for some positive integer . Let be a set of distinct points in the plane with a partition into subsets with (). This paper studies the problem of computing a planar polyline drawing of , such that each vertex of is mapped to a distinct point of . Lower and upper bounds on the number of bends per edge are proved for any . In the special case , we improve the upper and lower bounds presented in a paper by Pach and Wenger [J. Pach, R. Wenger, Embedding planar graphs at fixed vertex locations, Graphs and Combinatorics 17 (2001) 717–728]. The upper bound is based on an algorithm for computing a topological book embedding of a planar graph, such that the vertices follow a given left-to-right order and the number of crossings between every edge and the spine is asymptotically optimal, which can be regarded as a result of independent interest. [Copyright &y& Elsevier]

Abstract: In this paper, we study k-spine, h-bend planar drawings in which each vertex of a planar graph G lies on one of horizontal lines and each edge of G is drawn as a polyline containing at most bends. A graph with a k-spine, h-bend planar drawing is said to be k-spine, h-bend planar. We mainly focus on k-spine, 1-bend planar drawings, showing that for each , there exists a planar graph that is not k-spine, 1-bend planar, and furthermore, that it is -hard to test k-spine, 1-bend planarity. Given this complexity result, we further narrow our focus onto 2-spine, 1-bend planar drawings. We characterize 2-spine, 1-bend planarity using a new generalization of Hamiltonian graphs that we call Hamiltonian-with-handles graphs. We observe that our characterization naturally extends the connection between 2-page book embeddings and Hamiltonicity. Finally, we use our characterization to show that 2-outerplanar graphs are 2-spine, 1-bend planar. [Copyright &y& Elsevier]

Abstract: This paper studies the problem of computing orthogonal drawings of graphs with labels on vertices and edges. Our research is mainly motivated by Software Engineering and Information Systems domains, where tools like UML diagrams and ER-diagrams are considered fundamental for the design of sophisticated systems and/or complex data bases collecting enormous amount of information. A label is modeled as a rectangle of prescribed width and height and it can be associated with either a vertex or an edge. Our drawing algorithms guarantee no overlaps between labels, vertices, and edges and take advantage of the information about the set of labels to compute the geometry of the drawing. Several additional optimization goals are taken into account. Namely, the labeled drawing can be required to have either minimum total edge length, or minimum width, or minimum height, or minimum area among those preserving a given orthogonal representation. All these goals lead to NP-hard problems. We present MILP models to compute optimal drawings with respect to the first three goals and an exact algorithm that is based on these models to compute a labeled drawing of minimum area. We also present several heuristics for computing compact labeled orthogonal drawings and experimentally validate their performances, comparing their solutions against the optimum. [Copyright &y& Elsevier]

Let C be the family of 2D curves described by concave functions, let G be a planar graph, and let L be a linear ordering of the vertices of G. L is a curve embedding of G if for any given curve Λ∈C there exists a planar drawing of G such that: (i) the vertices are constrained to be on Λ with the same ordering as in L, and (ii) the edges are polylines with at most one bend. Informally speaking, a curve embedding can be regarded as a two-page book embedding in which the spine is bent. Although deciding whether a graph has a two-page book embedding is an NP-hard problem, in this paper it is proven that every planar graph has a curve embedding which can be computed in linear time. Applications of the concept of curve embedding to upward drawability and point-set embeddability problems are also presented. [Copyright &y& Elsevier]

Older adults are the main victims of the novel COVID-19 coronavirus outbreak and elderly in Long Term Care Facilities (LTCFs) are severely hit in terms of mortality. This paper presents a quantitative study of the impact of COVID-19 outbreak in Italy during first stages of the epidemic, focusing on the effects on mortality increase among older adults over 80 and its correlation with LTCFs. The study of growth patterns shows a power-law scaling regime for the first stage of the pandemic with an uneven behaviour among different regions as well as for the overall mortality increase according to the different impact of COVID-19. However, COVID-19 incidence rate does not fully explain the differences of mortality impact in older adults among different regions. We define a quantitative correlation between mortality in older adults and the number of people in LTCFs confirming the tremendous impact of COVID-19 on LTCFs. In addition a correlation between LTCFs and undiagnosed cases as well as effects of health system dysfunction is also observed. Our results confirm that LTCFs did not play a protective role on older adults during the pandemic, but the higher the number of elderly people living in LTCFs the greater the increase of both general and COVID-19 related mortality. We also observed that the handling of the crises in LTCFs hampered an efficient tracing of COVID-19 spread and promoted the increase of deaths not directly attributed to SARS-CoV-2. [ABSTRACT FROM AUTHOR]

The article focuses on a new model for algorithm animation over the world wide web. Algorithm animation helps the end user to understand algorithms by visually following their step-by-step execution, a complex task if relying on the textual program alone. There is a strong educational component associated with algorithm animation. It can be used by students individually or in class demonstrations. Algorithm animation is also a powerful software tool that can assist the algorithm designer in code debugging and in demonstrating a complex algorithm to a larger audience than merely specialists in the particular area of the algorithm. A new model, called Mocha, has been introduced for providing algorithm animation over the World-Wide Web. Mocha is a distributed model with a client-server architecture that optimally partitions the software components of a typical algorithm animation system and leverages the power of the Java language, an emerging standard for distributing interactive platform-independent multimedia applications across the Web.

A diagram is a drawing on the plane that represents a graph-like structure, where nodes are represented by symbols and edges are represented by curves connecting pairs of symbols. An automatic layout facility is a tool that receives as input a graph-like structure and is able to produce a diagram that nicely represents such a structure. Many systems use diagrams in the interaction with the users; thus, automatic layout facilities and algorithms for graphs layout have been extensively studied in the last years. We present a new approach in designing an automatic layout facility. Our approach is based on a modular management of a large collection of algorithms and on a strategy that, given the requirements of an application, selects a suitable algorithm for such requirements. The proposed approach has been used for designing the automatic layout facility of Diagram Server, a network server that offers to its clients several facilities for managing diagrams. [ABSTRACT FROM AUTHOR]

A simple topological graph is k -quasiplanar (k ≥ 2) if it contains no k pairwise crossing edges, and k -planar if no edge is crossed more than k times. In this paper, we explore the relationship between k -planarity and k -quasiplanarity to show that, for k ≥ 2 , every k -planar simple topological graph can be transformed into a (k + 1) -quasiplanar simple topological graph. [ABSTRACT FROM AUTHOR]

Background Frailty is associated with a prodromal stage called pre-frailty, a potentially reversible and highly prevalent condition before frailty becomes established. Despite this, there is no widely accepted definition of pre-frailty to support its early identification and management. This study applied an international consensus approach to define and better understand pre-frailty. Methods A modified electronic two-round Delphi Consensus study was conducted. In all, 23 experts from 12 countries with different backgrounds participated. The questionnaire was developed following a systematic literature review. An online consensus meeting was conducted with eight Delphi participants and two external experts. Qualitative and quantitative methods were employed for data analysis. An agreement level of 70% was applied for accepting statements. Results A total of 71 statements were circulated in Round 1. Of these, 52.8% were accepted. Fifty-one statements were re-circulated in Round 2, of which 92.1% were accepted. The online consensus meeting produced a consensus statement describing the concept, multi-factorial nature, and mechanism of pre-frailty as well as assessment, prevention and management approaches. All experts agreed that physical and non-physical factors such as psychological and social capacity are involved in the development of pre-frailty, potentially adversely affecting health and health-related quality of life outcomes. Practitioners should regard pre-frailty as a multi-factorial, multi-dimensional, and non-linear process that does not inevitably lead to frailty. It might be reversed or attenuated by targeted interventions. Brief, feasible and validated tools are recommended for opportunistic screening or case-finding followed by confirmation with multi-dimensional assessment. Conclusion It is difficult to establish consensus on one compact definition of pre-frailty, which is a multi-dimensional concept not only associated with physical impairment, but also with cognitive, nutritional, socioeconomic and other aspects of frailty. However, it may be too early to agree on an operational definition of pre-frailty since none yet exists for frailty. [ABSTRACT FROM AUTHOR]

Abstract A topological graph is a graph drawn in the plane. A topological graph is k -plane, k > 0 , if each edge is crossed at most k times. We study the problem of partitioning the edges of a k -plane graph such that each partite set forms a graph with a simpler structure. While this problem has been studied for k = 1 , we focus on optimal 2-plane and on optimal 3-plane graphs, which are 2-plane and 3-plane graphs with maximum density. We prove the following results. (i) It is not possible to partition the edges of a simple (i.e., with neither self-loops nor parallel edges) optimal 2-plane graph into a 1-plane graph and a forest, while (ii) an edge partition formed by a 1-plane graph and two plane forests always exists and can be computed in linear time. (iii) There exist efficient algorithms to partition the edges of a simple optimal 2-plane graph into a 1-plane graph and a plane graph with maximum vertex degree at most 12, or with maximum vertex degree at most 8 if the optimal2-plane graph is such that its crossing-free edges form a graph with no separating triangles. (iv) There exists an infinite family of simple optimal 2-plane graphs such that in any edge partition composed of a 1-plane graph and a plane graph, the plane graph has maximum vertex degree at least 6 and the 1-plane graph has maximum vertex degree at least 12. (v) Every optimal 3-plane graph whose crossing-free edges form a biconnected graph can be decomposed, in linear time, into a 2-plane graph and two plane forests. [ABSTRACT FROM AUTHOR]

Background Lowering mortality and hospitalization of older adults is one of the main goals of public health to improve both health systems' sustainability and older adults' quality of life. The aim of this study is to identify the determinants associated with mortality and the use of hospital services in the population older than 64 years of age. Methods A randomized sample from the population of the Lazio region (Italy) above the age of 64 was enrolled in 2014 by the administration of a questionnaire to assess frailty; the rates of use of hospital services and mortality in the year following the enrolment have been retrieved by the regional database. Univariable and multivariable analyses addressed the association of health status, social and economic variables with health outcomes. Results One thousand two hundred and eighty persons were recruited; 52 deaths were reported at 1 year of follow-up (robust 1.8%, frail 10.1% and very frail 19.1%, P < 0.001). The mean rate of use of hospital services was 692.2 per 1000 observation/year (robust 589.5, frail 1191.1 and very frail 848.4, P < 0.001). In the multivariate analysis, the higher rate of use of hospital services was independently associated with functional status, social support, psychological/psychiatric discomfort, availability of home care services and physical health. Conclusions Frailty, as a multidimensional issue, is also a strong predictor of survival in the short term. The use of the hospital services by older adults is associated mainly with functional status, social resources, psycho-physical status and health service organization factors. [ABSTRACT FROM AUTHOR]

Visibility representations are a well-known paradigm to represent graphs. From a high-level perspective, a visibility representation of a graph G maps the vertices of G to non-overlapping geometric objects and the edges of G to visibilities, i.e., segments that do not intersect any geometric object other than at their end-points. In this paper, we initiate the study of 2.5D box visibility representations (2.5D-BRs) where vertices are mapped to 3D boxes having the bottom face in the plane z = 0 and edges are unobstructed lines of sight parallel to the x - or y -axis. We prove that: ( i ) Every complete bipartite graph admits a 2.5D-BR; ( i i ) The complete graph K n admits a 2.5D-BR if and only if n ⩽ 19 ; ( i i i ) Every graph with pathwidth at most 7 admits a 2.5D-BR, which can be computed in linear time. We then turn our attention to 2.5D grid box representations (2.5D-GBRs), which are 2.5D-BRs such that the bottom face of every box is a unit square at integer coordinates. We show that an n -vertex graph that admits a 2.5D-GBR has at most 4 n − 6 n edges and this bound is tight. Finally, we prove that deciding whether a given graph G admits a 2.5D-GBR with a given footprint is NP-complete (the footprint of a 2.5D-BR Γ is the set of bottom faces of the boxes in Γ). [ABSTRACT FROM AUTHOR]

A 1 -plane graph is a graph embedded in the plane such that each edge is crossed at most once. A NIC-plane graph is a 1-plane graph such that any two pairs of crossing edges share at most one end-vertex. An edge partition of a 1-plane graph G is a coloring of the edges of G with two colors, red and blue, such that both the graph induced by the red edges and the graph induced by the blue edges are plane graphs. We prove the following: ( i ) Every NIC-plane graph admits an edge partition such that the red graph has maximum vertex degree three; this bound on the vertex degree is worst-case optimal. ( ii ) Deciding whether a NIC-plane graph admits an edge partition such that the red graph has maximum vertex degree two is NP-complete. ( iii ) Deciding whether a 1-plane graph admits an edge partition such that the red graph has maximum vertex degree one, and computing one in the positive case, can be done in quadratic time. Applications of these results to graph drawing are also discussed. [ABSTRACT FROM AUTHOR]