Search results for "Graph drawing"
showing 5 items of 15 documents
An Aggressive Search Procedure for the Bipartite Drawing Problem
1996
Graphs are used to represent reality in several areas of knowledge. This has generated considerable interest in graph drawing algorithms. Arc crossing minimization is a fundamental aesthetic criterion to obtain a readable map of a graph. The problem of minimizing the number of arc crossings in a bipartite graph (BDP) is NP-complete. In this paper we present an aggressive search scheme for the BDP based on the Intensification, Diversification and Strategic Oscillation elements of Tabu Search. Several algorithms can be obtained with this scheme by implementing different evaluators in the move definitions. In this paper we propose two variants. Computational results are reported on a set of 30…
Incremental bipartite drawing problem
2001
Abstract Layout strategies that strive to preserve perspective from earlier drawings are called incremental. In this paper we study the incremental arc crossing minimization problem for bipartite graphs. We develop a greedy randomized adaptive search procedure (GRASP) for this problem. We have also developed a branch-and-bound algorithm in order to compute the relative gap to the optimal solution of the GRASP approach. Computational experiments are performed with 450 graph instances to first study the effect of changes in grasp search parameters and then to test the efficiency of the proposed procedure. Scope and purpose Many information systems require graphs to be drawn so that these syst…
Tabu search for the dynamic Bipartite Drawing Problem
2018
Abstract Drawings of graphs have many applications and they are nowadays well-established tools in computer science in general, and optimization in particular. Project scheduling is one of the many areas in which representation of graphs constitutes an important instrument. The experience shows that the main quality desired for drawings of graphs is readability, and crossing reduction is a fundamental aesthetic criterion to achieve it. Incremental or dynamic graph drawing is an emerging topic in this context, where we seek to preserve the layout of a graph over successive drawings. In this paper, we target the edge crossing reduction in the context of incremental graph drawing. Specifically…
Heuristics for the Constrained Incremental Graph Drawing Problem
2019
Abstract Visualization of information is a relevant topic in Computer Science, where graphs have become a standard representation model, and graph drawing is now a well-established area. Within this context, edge crossing minimization is a widely studied problem given its importance in obtaining readable representations of graphs. In this paper, we focus on the so-called incremental graph drawing problem, in which we try to preserve the user’s mental map when obtaining successive drawings of the same graph. In particular, we minimize the number of edge crossings while satisfying some constraints required to preserve the position of vertices with respect to previous drawings. We propose heur…
Visualizing linguistic variation in a network of Latin documents and scribes
2018
This article explores whether and how network visualization can benefit philological and historical-linguistic study. This is illustrated with a corpus-based investigation of scribes' language use in a lemmatized and morphologically annotated corpus of documentary Latin (Late Latin Charter Treebank, LLCT2). We extract four continuous linguistic variables from LLCT2 and utilize a gradient colour palette in Gephi to visualize the variable values as node attributes in a trimodal network which consists of the documents, writers, and writing locations underlying the same corpus. We call this network the "LLCT2 network". The geographical coordinates of the location nodes form an approximate map, …