103 research outputs found
Parameterized Complexity of Two-Interval Pattern Problem
Get PDFA 2-interval is the union of two disjoint intervals on the real line. Two 2-intervals D₁ and D₂ are disjoint if their intersection is empty (i.e., no interval of D₁ intersects any interval of D₂). There can be three different relations between two disjoint 2-intervals; namely, preceding (<), nested (⊏) and crossing (≬). Two 2-intervals D₁ and D₂ are called R-comparable for some R∈{<,⊏,≬}, if either D₁RD₂ or D₂RD₁. A set of disjoint 2-intervals is ℛ-comparable, for some ℛ⊆{<,⊏,≬} and ℛ≠∅, if every pair of 2-intervals in ℛ are R-comparable for some R∈ℛ. Given a set of 2-intervals and some ℛ⊆{<,⊏,≬}, the objective of the {2-interval pattern problem} is to find a largest subset of 2-intervals that is ℛ-comparable.
The 2-interval pattern problem is known to be W[1]-hard when |ℛ|=3 and NP-hard when |ℛ|=2 (except for ℛ={<,⊏}, which is solvable in quadratic time). In this paper, we fully settle the parameterized complexity of the problem by showing that it is W[1]-hard for both ℛ={⊏,≬} and ℛ={<,≬} (when parameterized by the size of an optimal solution). This answers the open question posed by Vialette [Encyclopedia of Algorithms, 2008]
Boundary Labeling for Rectangular Diagrams
Get PDFGiven a set of n points (sites) inside a rectangle R and n points (label locations or ports) on its boundary, a boundary labeling problem seeks ways of connecting every site to a distinct port while achieving different labeling aesthetics. We examine the scenario when the connecting lines (leaders) are drawn as axis-aligned polylines with few bends, every leader lies strictly inside R, no two leaders cross, and the sum of the lengths of all the leaders is minimized. In a k-sided boundary labeling problem, where 1 <= k <= 4, the label locations are located on the k consecutive sides of R.
In this paper we develop an O(n^3 log n)-time algorithm for 2-sided boundary labeling, where the leaders are restricted to have one bend. This improves the previously best known O(n^8 log n)-time algorithm of Kindermann et al. (Algorithmica, 76(1):225-258, 2016). We show the problem is polynomial-time solvable in more general settings such as when the ports are located on more than two sides of R, in the presence of obstacles, and even when the objective is to minimize the total number of bends. Our results improve the previous algorithms on boundary labeling with obstacles, as well as provide the first polynomial-time algorithms for minimizing the total leader length and number of bends for 3- and 4-sided boundary labeling. These results settle a number of open questions on the boundary labeling problems (Wolff, Handbook of Graph Drawing, Chapter 23, Table 23.1, 2014)
Visualizing graphs: optimization and trade-offs
Get PDFEffective visualization of graphs is a powerful tool to help understand the relationships among the graph's underlying objects and to interact with them. Several styles for drawing graphs have emerged over the last three decades. Polyline drawing is a widely used style for drawing graphs, where each node is mapped to a distinct point in the plane and each edge is mapped to a polygonal chain between their corresponding nodes. Some common optimization criteria for such a drawing are defined in terms of area requirement, number of bends per edge, angular resolution, number of distinct line segments, edge crossings, and number of planar layers. In this thesis we develop algorithms for drawing graphs that optimize different aesthetic qualities of the drawing. Our algorithms seek to simultaneously optimize multiple drawing aesthetics, reveal potential trade-offs among them, and improve many previous graph drawing algorithms. We start by exploring probable trade-offs in the context of planar graphs. We prove that every -vertex planar triangulation with maximum degree can be drawn with at most segments and area, where is the number of leaves in a Schnyder tree of . We then show that one can improve the area by allowing the edges to have bends. Since compact drawings often suffer from bad angular resolution, we seek to compute polyline drawings with better angular resolution. We develop a polyline drawing algorithm that is simple and intuitive, yet implies significant improvement over known results. At this point we move our attention to drawing nonplanar graphs. We prove that every thickness- graph can be drawn on planar layers with bends per edge, where . Previously, the bend complexity, i.e., the number of bends per edge, was not known to be sublinear for . We then examine the case when the number of available layers is restricted. The layers may now contain edge crossings. We develop a technique to draw complete graphs on two layers, which improves previous upper bounds on the number of edge crossings in such drawings.October 201
Exploring Associations between Sense of Place and Depression among Military Veterans
Get PDFWith a population exceeding 18 million (United States Department of Veterans Affairs, 2008), depression stands out as a main mental health challenge among veterans (Liu, Collins, Wang, Xie, & Bie, 2019). This research aimed to understand if leaving the military, disturbing the bond between the military environment and its service members, has any contribution to depression after discharge. The sense of place theory was applied in this research to address this query. The multi-disciplinary study focused on the main research question of whether there is a significant relationship between a sense of place in the military and depression. A quantitative study design and cross-sectional strategies were adopted to answer this question. The study found a plausible explanatory pathway between a sense of place and post-discharge depression among veterans. The study's suggested conceptual model of a sense of place was then applied to the context of the military. Among the suggested subdimensions of sense of place in the military (identity, landscape, housing type, and socializing and active engagement), identity had a significant role in the relationship between sense of place and depression.
This finding can open an opportunity for an in-depth methodology to provide practical insights that would benefit environmental designers, architects, and related professionals in equipping and designing environments for veterans.Embargo status: Restricted until 06/2025. To request the author grant access, click on the PDF link to the left
Highly conducting p-type nanocrystalline silicon thin films preparation without additional hydrogen dilution
No full text
Low temperature growth of carbon nanotubes with aligned multiwalls by microwave plasma-CVD
No full text
- …
