Cologne Excellence Cluster on Cellular Stress Responses in Aging Associated Diseases
Graph Drawing E-print ArchiveNot a member yet
1225 research outputs found
Sort by
Flips
No full textWe review results concerning edge flips in triangulations concentrating mainly on various aspects of the following question: Given two different triangulations of the same size, how many edge flips are necessary and sufficient to transform one triangulation into the other? We focus both on the combinatorial perspective (where only a combinatorial embedding of the graph is specified) and the geometric perspective (where the graph is embedded in the plane, vertices are points and edges are straight-line segments). We highlight some of the techniques used to prove the main results and mention a few of the challenges remaining in this area
StreamEB: Stream Edge Bundling
No full textGraph streams have been studied extensively, such as for data mining, while fairly limitedly for visualizations. Recently, edge bundling promises to reduce visual clutter in large graph visualizations, though mainly focusing on static graphs.
This paper presents a new framework, namely StreamEB, for edge bundling of graph streams, which integrates temporal, neighbourhood, data-driven and spatial compatibility for edges. Amongst these metrics, temporal and neighbourhood compatibility are introduced for the first time. We then present force-directed and tree-based methods for stream edge bundling. The effectiveness of our framework is then demonstrated using US flights data and Thompson-Reuters stock data
Interactive Random Graph Generation with Evolutionary Algorithms
No full textThis paper introduces an interactive system called GraphCuisine that lets users steer an Evolutionary Algorithm (EA) to create random graphs that match user-specified measures. Generating random graphs with particular characteristics is crucial for evaluating graph algorithms, layouts and visualization techniques. Current random graph generators provide limited control of the final characteristics of the graphs they generate. The situation is even harder when one wants to generate random graphs similar to a given one, all-in-all leading to a long iterative process that involves several steps of random graph generation, parameter changes, and visual inspection. Our system follows an approach based on interactive evolutionary computation. Fitting generator parameters to create graphs with pre-defined measures is an optimization problem, while assessing the quality of the resulting graphs often involves human subjective judgment. In this paper we describe the graph generation process from a user’s perspective, provide details about our evolutionary algorithm, and demonstrate how GraphCuisine is employed to generate graphs that mimic a given real-world network. An interactive demo of GraphCuisine can be found on our website http://www.aviz.fr/Research/Graphcuisine
Upward Planarity Testing: A Computational Study
No full textA directed acyclic graph (DAG) is upward planar if it can be drawn without any crossings while all edges—when following them in their direction—are drawn with strictly monotonously increasing y-coordinates. Testing whether a graph allows such a drawing is known to be NP-complete, but there is a substantial collection of different algorithmic approaches known in literature.
In this paper, we give an overview of the known algorithms, ranging from combinatorial FPT and branch-and-bound algorithms to ILP and SAT formulations. Most approaches of the first class have only been considered from the theoretical point of view, but have never been implemented. For the first time, we give an extensive experimental comparison between virtually all known approaches to the problem.
Furthermore, we present a new SAT formulation based on a recent theoretical result by Fulek et al. [8], which turns out to perform best among all known algorithms
A Linear-Time Algorithm for Testing Outer-1-Planarity
No full textA graph is 1-planar if it can be embedded in the plane with at most one crossing per edge. 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 graph is outer-1-planar. The algorithm can be used to produce an outer-1-planar embedding in linear time if it exists
Recognizing Outer 1-Planar Graphs in Linear Time
No full textA graph is outer 1-planar (o1p) if it can be drawn in the plane such that all vertices are on the outer face and each edge is crossed at most once. o1p graphs generalize outerplanar graphs, which can be recognized in linear time and specialize 1-planar graphs, whose recognition is NP -hard.
Our main result is a linear-time algorithm that first tests whether a graph G is o1p, and then computes an embedding. Moreover, the algorithm can augment G to a maximal o1p graph. If G is not o1p, then it includes one of six minors (see Fig. 3), which are also detected by the recognition algorithm. Hence, the algorithm returns a positive or negative witness for o1p
Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices
No full textA simultaneous embedding of two graphs G\textcircled{1} and G\textcircled{2} with common graph G=G\textcircled{1}∩G\textcircled{2} is a pair of planar drawings of G\textcircled{1} and G\textcircled{2} that coincide on G. It is an open question whether there is a polynomial-time algorithm that decides whether two graphs admit a simultaneous embedding (problem Sefe).
In this paper, we present two results. First, a set of three linear-time preprocessing algorithms that remove certain substructures from a given Sefe instance, producing a set of equivalent Sefe instances without such substructures. The structures we can remove are (1) cutvertices of the union graph G\textcircled{1}∪G\textcircled{2} , (2) cutvertices that are simultaneously a cutvertex in G\textcircled{1} and G\textcircled{2} and that have degree at most 3 in G, and (3) connected components of G that are biconnected but not a cycle.
Second, we give an O(n 2)-time algorithm for Sefe where, for each pole u of a P-node μ (of a block) of the input graphs, at most three virtual edges of μ contain common edges incident to u. All algorithms extend to the sunflower case
Drawing Planar Graphs with a Prescribed Inner Face
No full textGiven a plane graph G (i.e., a planar graph with a fixed planar embedding) and a simple cycle C in G whose vertices are mapped to a convex polygon, we consider the question whether this drawing can be extended to a planar straight-line drawing of G. We characterize when this is possible in terms of simple necessary conditions, which we prove to be sufficient. This also leads to a linear-time testing algorithm. If a drawing extension exists, it can be computed in the same running time
Fixed Parameter Tractability of Crossing Minimization of Almost-Trees
No full textWe investigate exact crossing minimization for graphs that differ from trees by a small number of additional edges, for several variants of the crossing minimization problem. In particular, we provide fixed parameter tractable algorithms for the 1-page book crossing number, the 2-page book crossing number, and the minimum number of crossed edges in 1-page and 2-page book drawings