Search

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]

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]

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]

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]

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]

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]

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]

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]

An ortho-polygon visibility representation of an n-vertex embedded graph G (OPVR of G) is an embedding-preserving drawing of G that maps every vertex to a distinct orthogonal polygon and each edge to a vertical or horizontal visibility between its end-vertices. The vertex complexity of an OPVR of G is the minimum k such that every polygon has at most k reflex corners. We present polynomial time algorithms that test whether G has an OPVR and, if so, compute one of minimum vertex complexity. We argue that the existence and the vertex complexity of an OPVR of G are related to its number of crossings per edge and to its connectivity. More precisely, we prove that if G has at most one crossing per edge (i.e., G is a 1-plane graph), an OPVR of G always exists while this may not be the case if two crossings per edge are allowed. Also, if G is a 3-connected 1-plane graph, we can compute an OPVR of G whose vertex complexity is bounded by a constant in O(n) time. However, if G is a 2-connected 1-plane graph, the vertex complexity of any OPVR of G may be Ω(n). In contrast, we describe a family of 2-connected 1-plane graphs for which an embedding that guarantees constant vertex complexity can be computed in O(n) time. Finally, we present the results of an experimental study on the vertex complexity of ortho-polygon visibility representations of 1-plane graphs. [ABSTRACT FROM AUTHOR]

For a graph G, a function ψ is called a bar visibility representation of G when for each vertex v∈V(G), ψ(v) is a horizontal line segment (bar) and uv∈E(G) if and only if there is an unobstructed, vertical, ε-wide line of sight between ψ(u) and ψ(v). Graphs admitting such representations are well understood (via simple characterizations) and recognizable in linear time. For a directed graph G, a bar visibility representation of G, additionally, puts the bar ψ(u) strictly below the bar ψ(v) for each directed edge (u, v) of G. We study a generalization of the recognition problem where a function ψ′ defined on a subset V′ of V(G) is given and the question is whether there is a bar visibility representation ψ of G with ψ(v)=ψ′(v) for every v∈V′. We show that for undirected graphs this problem, and other closely related problems, is NP-complete, but for certain cases involving directed graphs it is solvable in polynomial time. [ABSTRACT FROM AUTHOR]

Motivated by applications in graph drawing and information visualization, we examine the planar split thickness of a graph, that is, the smallest k such that the graph is k-splittable into a planar graph. A k-split operation substitutes a vertex v by at most k new vertices such that each neighbor of v is connected to at least one of the new vertices. We first examine the planar split thickness of complete graphs, complete bipartite graphs, multipartite graphs, bounded degree graphs, and genus-1 graphs. We then prove that it is NP-hard to recognize graphs that are 2-splittable into a planar graph, and show that one can approximate the planar split thickness of a graph within a constant factor. If the treewidth is bounded, then we can even verify k-splittability in linear time, for a constant k. [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 graph is k-planar ]> ]> ( k ≥ 1 ) ]> if it can be drawn in the plane such that no edge is crossed ]> ]> k + 1 ]> times or more. A graph is k-quasi-planar ]> ]> ( k ≥ 2 ) ]> if it can be drawn in the plane with no k pairwise crossing edges. The families of k-planar and k-quasi-planar graphs have been widely studied in the literature, and several bounds have been proven on their edge density. Nonetheless, only trivial results are known about the relationship between these two graph families. In this paper we prove that, for ]> ]> k ≥ 3 ]> , every k-planar graph is ]> ]> ( k + 1 ) ]> -quasi-planar. [ABSTRACT FROM AUTHOR]

A graph is 1-planar if it can be embedded in the plane with at most one crossing per edge. It is known that the problem of testing 1-planarity of a graph is NP-complete. In this paper, we study outer-1-planar graphs. A graph is outer-1-planar if it has an embedding in which every vertex is on the outer face and each edge has at most one crossing. We present a linear time algorithm to test whether a given graph is outer-1-planar. The algorithm can be used to produce an outer-1-planar embedding in linear time if it exists. [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]

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]