We show how to compute a maximum upward planar single-source subgraph of a single-source embedded DAG
G
φ
. We first show that finding a maximum upward planar subgraph of a single-source embedded ...digraph is NP-complete. We then give a new characterization of upward planar single-source digraphs. We use this characterization to present an algorithm that computes a maximum upward planar single-source subgraph of a single-source embedded DAG. This algorithm takes
O
(
n
4
) time in the worst case and
O
(
n
3
) time on average.
Modern visual analytics tools provide mechanism for users to gain unknown knowledge through effective visual interactions for user to quickly understand the progress of algorithms and adjust the ...input parameters on intermediate visualizations that towards the production of most satisfied outcome. This requires the quick production of a sequence of graph visualizations. However, the traditional force-directed graph drawing algorithms are very slow to reach an equilibrium configuration of forces. They usually spend tens of seconds producing the layout of a graph converge. Thus, they do not satisfy the requirement of rapid drawing of graphs. This paper proposes a fast convergence method for drawing force-directed graphs. We essentially pre-calculate the geometrical position of all vertices before applying a force-directed layout algorithm to reach the energy minimization of the graph layout. The experimental results have shown that this approach could not only reduce the convergence time but also the number of edge crossings that approves the quality of layout significantly.
Force-directed approach is one of the most widely used methods in graph drawing research. There are two main problems with the traditional force-directed algorithms. First, there is no mature theory ...to ensure the convergence of iteration sequence used in the algorithm and further, it is hard to estimate the rate of convergence even if the convergence is satisfied. Second, the running time cost is increased intolerablely in drawing largescale graphs, and therefore the advantages of the force-directed approach are limited in practice. This paper is focused on these problems and presents a sufficient condition for ensuring the convergence of iterations. We then develop a practical heuristic algorithm for speeding up the iteration in force-directed approach using a successive over-relaxation （SOR） strategy. The results of computational tests on the several benchmark graph datasets used widely in graph drawing research show that our algorithm can dramatically improve the performance of force-directed approach by decreasing both the number of iterations and running time, and is 1.5 times faster than the latter on average.
One Graph, Multiple Drawings Nadal, M.; Melanon, G.
2013 17th International Conference on Information Visualisation,
2013-July
Conference Proceeding
Being able to produce a wide variety of layouts for a same graphs may prove useful when users have no preferred visual encoding for their data. The first contribution of this paper is a enhanced ...force-directed layout capable of producing different layouts of a same graph. We turn a well known force-directed algorithm (GEM) into a highly parametrizable layout and control it from a genetic algorithm framework. The genetic algorithm allows to efficiently explore the parameter space of this highly parametrisable layout. The search process relies on the capability of the system to evaluate the similarity between two drawings. The second contribution of this paper is a similarity metric used as a fitness function for the genetic algorithm. Its main features are its computational cost and its insensitivity to planar homotheties.
A straight-line drawing of a plane graph is called an open rectangle-of-influence drawing if there is no vertex in the proper inside of the axis-parallel rectangle defined by the two ends of every ...edge. In an inner triangulated plane graph, every inner face is a triangle although the outer face is not necessarily a triangle. In this paper, we first obtain a sufficient condition for an inner triangulated plane graph
G
to have an open rectangle-of-influence drawing; the condition is expressed in terms of a labeling of angles of a subgraph of
G
. We then present an
O
(
n
1.5
/log
n
)-time algorithm to examine whether
G
satisfies the condition and, if so, construct an open rectangle-of-influence drawing of
G
on an (
n
−1)×(
n
−1) integer grid, where
n
is the number of vertices in
G
.
This Demonstration paper discusses ongoing work at Tom Sawyer Software in the area of advanced visualization and analysis of very large data sets, including RDF data. There is a growing imperative to ...explore large data sets as part of opportunity and threat analysis in areas such as national defense, financial risk analysis, market intelligence, and disease epidemiology. An increasing volume of this type of information is represented as RDF graphs. By visualizing and visually analyzing data, it is possible to see patterns, trends, and outliers in complex RDF graphs that would otherwise be difficult or even impossible to discover. Since RDF graphs are by nature difficult for humans to read, Tom Sawyer Software has been developing an innovative, graphical approach to defining the schema of RDF data, visualizing salient parts of the RDF graph, and integrating social network analysis into the visualization process to provide intuitive visual navigation, query, and understanding of information. This Demonstration paper discusses the underlying technology and its realization in sophisticated software for building advanced data visualization and analysis applications for making sense of large RDF graphs.
PDF
