1,721,076 research outputs found
Fast layout computation of clustered networks: Algorithmic advances and experimental analysis
No full textThe visual analysis of large and complex relational data sets is a growing need in many application domains, such as social sciences, biology, computer networks, and software engineering. In this respect, the capability of quickly computing two-dimensional layouts of hierarchically clustered networks plays an important role and should be a major requirement of many graph visualization systems. We present algorithmic and experimental advances on the subject, namely: (i) we propose a new drawing algorithm that combines space-filling and fast force-directed methods; it runs in O(n log n + m) time, where n and m are the number of vertices and edges of the network, respectively. This running time does not depend on the number of clusters, thus the algorithm guarantees good time performance independently of the structure of the cluster hierarchy. As a further advantage, the algorithm can be easily parallelized. (ii) We discuss the results of an experimental analysis aimed at understanding which clustering algorithms can be used in combination with our visualization technique to generate better quality drawings for small-world and scale-free networks of medium and large size. As far as we know, no previous similar experiments have been done to this aim
Vis4AUI: Visual Analysis of Banking Activity Networks
No full textWe present the system VIS4AUI, aimed at supporting the analyst to discover financial crimes related to money
laundering. An anti-money laundering archive collects financial information with regard to ongoing bank relationships
and high value transactions. VIS4AUI is able to import and analyze the Italian anti-money laundering
archive (AUI) in order to visualize the banking activity networks arising from it. In the demonstration,
the user will be given an evidence of a possible suspicious person or company; starting from such a seed
entity, the task will be that of exploring and analyzing her network of transactions through the tools provided
by the system. In order to immerse the user in a fully interactive experience, VIS4AUI is a touch-optimized
application, only requiring a touch-screen as interface
Orthogonal planarity testing of bounded treewidth graphs
No full textGiven 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(n3logn) time, which improves on the previous O(n4) bounds for these two
A survey on graph drawing beyond planarity
No full textGraph 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
Simultaneous visibility representations of plane st-graphs using L-shapes
No full textLet 〈 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
Fast Layout Computation of Hierarchically Clustered Networks: Algorithmic Advances and Experimental Analysis
No full textFast computation of two-dimensional layouts of hierarchically
clustered networks is a well-studied problem in graph visualization. We present algorithmic and experimental advances on the subject: (i) We propose a new drawing algorithm that combines space-filling and fast force-directed methods; it runs in O(nlogn+m) time, where n and m are the number of vertices and edges of the network, respectively. This running time does not depend on the number of clusters, thus the algorithm guarantees
good time performances independently of the structure of the cluster hierarchy. As a further advantage, the algorithm can be easily parallelized. (ii) We present an experimental analysis aimed at understanding which clustering algorithms can be used in combination with our visualization technique to generate better quality drawings for medium and large networks with small-world and scalefree structure. As far as we know, no previous similar experiments have been done in this respect
Large graph visualizations using a distributed computing platform
No full textBig Data analytics is recognized as one of the major issues in our current information society, and raises several challenges and opportunities in many fields, including economy and finance, e-commerce, public health and administration, national security, and scientific research. The use of visualization techniques to make sense of large volumes of information is an essential ingredient, especially for the analysis of complex interrelated data, which are represented as graphs. The growing availability of powerful and inexpensive cloud computing services naturally motivates the study of distributed graph visualization algorithms, able to scale to the size of large graphs. We study the problem of designing a distributed visualization algorithm that must be simple to implement and whose computing infrastructure does not require major hardware or software investments. We design, implement, and experiment a force-directed algorithm in Giraph, a popular open source framework for distributed computing, based on a vertex-centric design paradigm. The algorithm is tested both on real and artificial graphs with up to one million edges. The experiments show the scalability and effectiveness of our technique when compared to a centralized implementation of the same force-directed model. Graphs with about one million edges can be drawn in a few minutes, by spending about 1 USD per drawing with a cloud computing infrastructure of Amazon
L-Visibility Drawings of IC-Planar Graphs
No full textAn IC-plane graph is a topological graph where every edge is crossed at most once and no two crossed edges share a vertex. We show that every IC-plane graph has a visibility drawing where every vertex is of the form of s suitably oriented "L", and every edge is either a horizontal or vertical segment. As a byproduct of our drawing technique, we prove that every IC-plane graph has a RAC drawing in quadratic area with at most two bends per edge
- …
