A tabu search based approach for graph layout

This paper describes an automated tabu search based method for drawing general graph layouts with straight lines. To our knowledge, this is the first time tabu methods have been applied to graph drawing. We formulated the task as a multi-criteria optimization problem with a number of metrics which are used in a weighted fitness function to measure the aesthetic quality of the graph layout. The main goal of this work is to speed up the graph layout process without sacrificing layout quality. To achieve this, we use a tabu search based method that goes through a predefined number of iterations to minimize the value of the fitness function. Tabu search always chooses the best solution in the neighbourhood. This may lead to cycling, so a tabu list is used to store moves that are not permitted, meaning that the algorithm does not choose previous solutions for a set period of time. We evaluate the method according to the time spent to draw a graph and the quality of the drawn graphs. We give experimental results applied on random graphs and we provide statistical evidence that our method outperforms a fast search-based drawing method (hill climbing) in execution time while it produces comparably good graph layouts. We also demonstrate the method on real world graph datasets to show that we can reproduce similar results in a real world setting.     

基于图匹配的分层布局算法

针对节点数目较大并且度数比较平均的无向图,根据分层扩展的思想,提出一种基于图匹配的分层布局算法（Graph Matching Hierarchy,GMH）。基于图匹配思想对大图进行递归化简,然后应用FR算法对最粗化图进行布局,最后利用质心布局算法对图进行扩展。实验结果表明,GMH算法能够提高可视化效率,改善布局效果,且分层布局的结果更易于理解。      

A memetic algorithm for the cyclic antibandwidth maximization problem

The cyclic antibandwidth problem is to embed the vertices of a graph G of n vertices on a cycle C _n such that the minimum distance (measured in the cycle) of adjacent vertices is maximized. Exact results/conjectures for this problem exist in the literature for some standard graphs, such as paths, cycles, two-dimensional meshes, and tori, but no algorithm has been proposed for the general graphs in the literature reviewed by us so far. In this paper, we propose a memetic algorithm for the cyclic antibandwidth problem (MACAB) that can be applied on arbitrary graphs. An important feature of this algorithm is the use of breadth first search generated level structures of a graph to explore a variety of solutions. A novel greedy heuristic is designed which explores these level structures to label the vertices of the graph. The algorithm achieves the exact cyclic antibandwidth of all the standard graphs with known optimal values. Based on our experiments we conjecture the cyclic antibandwidth of three-dimensional meshes, hypercubes, and double stars. Experiments show that results obtained by MACAB are substantially better than those given by genetic algorithm.     

Drawing complete binary trees inside rectilinear polygons

Most of graph drawing algorithms draw graphs on unbounded planes. However, there are applications that require graphs to be drawn on the plane inside a given polygon. In this paper, a new algorithm for planar orthogonal drawing of complete binary trees inside rectilinear polygons is presented. Uniform distribution of nodes of graphs on drawing regions is one of the aesthetics criteria in graph drawing. The goal of this paper is to produce planar orthogonal drawings with a relatively uniform node distribution and few edge bends. The proposed algorithm can be considered as a generalization of the H-tree layout method for rectilinear polygons. A new linear time algorithm is also given for bisecting rectilinear polygons into two equi-area rectilinear sub-polygons.     

On the coding of ordered graphs

Ordered graph and ordered graph isomorphism provide a natural representation of many objects in applications such as computational geometry, computer vision and pattern recognition. In the present paper we propose a coding procedure for ordered graphs that improves an earlier one based on Eulerian circuits of graphs in terms of both simplicity and computational efficiency. Using our coding approach, we show that the ordered graph isomorphism problem can be optimally solved in quadratic time, although no efficient (polynomial-bound) isomorphism algorithm for general graphs exists today. An experimental evaluation demonstrates the superior performance of the new method.     

Sum Coloring Interval and k -Claw Free Graphs with Application to Scheduling Dependent Jobs

We consider the sum coloring and sum multicoloring problems on several fundamental classes of graphs, including the classes of interval and k-claw free graphs. We give an algorithm that approximates sum coloring within a factor of 1.796, for any graph in which the maximum k-colorable subgraph problem is polynomially solvable. In particular, this improves on the previous best known ratio of 2 for interval graphs. We introduce a new measure of coloring, robust throughput}, that indicates how quickly the graph is colored, and show that our algorithm approximates this measure within a factor of 1.4575. In addition, we study the contiguous (or non-preemptive) sum multicoloring problem on k-claw free graphs. This models, for example, the scheduling of dependent jobs on multiple dedicated machines, where each job requires the exclusive use of at most k machines. Assuming that k is a fixed constant, we obtain the first constant factor approximation for the problem.     

GO: A cluster algorithm for graph visualization

As we are in the big data age, graph data such as user networks in Facebook and Flickr becomes large. How to reduce the visual complexity of a graph layout is a challenging problem. Clustering graphs is regarded as one of effective ways to address this problem. Most of current graph visualization systems, however, directly use existing clustering algorithms that are not originally developed for the visualization purpose. For graph visualization, a clustering algorithm should meet specific requirements such as the sufficient size of clusters, and automatic determination of the number of clusters. After identifying the requirements of clustering graphs for visualization, in this paper we present a new clustering algorithm that is particularly designed for visualization so as to reduce the visual complexity of a layout, together with a strategy for improving the scalability of our algorithm. Experiments have demonstrated that our proposed algorithm is capable of detecting clusters in a way that is required in graph visualization.     

The Longest Path Problem has a Polynomial Solution on Interval Graphs

The longest path problem is the problem of finding a path of maximum length in a graph. Polynomial solutions for this problem are known only for small classes of graphs, while it is NP-hard on general graphs, as it is a generalization of the Hamiltonian path problem. Motivated by the work of Uehara and Uno (Proc. of the 15th Annual International Symp. on Algorithms and Computation (ISAAC), LNCS, vol. 3341, pp. 871–883, 2004), where they left the longest path problem open for the class of interval graphs, in this paper we show that the problem can be solved in polynomial time on interval graphs. The proposed algorithm uses a dynamic programming approach and runs in O(n ⁴) time, where n is the number of vertices of the input graph.     

Smashing peacocks further: drawing quasi-trees from biconnected components

We extend the popular force-directed approach to network (or graph) layout to allow separation constraints, which enforce a minimum horizontal or vertical separation between selected pairs of nodes. This simple class of linear constraints is expressive enough to satisfy a wide variety of application-specific layout requirements, including: layout of directed graphs to better show flow; layout with non-overlapping node labels; and layout of graphs with grouped nodes (called clusters). In the stress majorization force-directed layout process, separation constraints can be treated as a quadratic programming problem. We give an incremental algorithm based on gradient projection for efficiently solving this problem. The algorithm is considerably faster than using generic constraint optimization techniques and is comparable in speed to unconstrained stress majorization. We demonstrate the utility of our technique with sample data from a number of practical applications including gene-activation networks, terrorist networks and visualization of high-dimensional data     

Improving multiple aesthetics produces better graph drawings

Many automatic graph drawing algorithms implement only one or two aesthetic criteria since most aesthetics conflict with each other. Empirical research has shown that although those algorithms are based on different aesthetics, drawings produced by them have comparable effectiveness.The comparable effectiveness raises a question about the necessity of choosing one algorithm against another for drawing graphs when human performance is a main concern. In this paper, we argue that effectiveness can be improved when algorithms are designed by making compromises between aesthetics, rather than trying to satisfy one or two of them to the fullest. We therefore introduce a new algorithm: BIGANGLE. This algorithm produces drawings with multiple aesthetics being improved at the same time, compared to a classical spring algorithm. A user study comparing these two algorithms indicates that BIGANGLE induces a significantly better task performance and a lower cognitive load, therefore resulting in better graph drawings in terms of human cognitive efficiency.Our study indicates that aesthetics should not be considered separately. Improving multiple aesthetics at the same time, even to small extents, will have a better chance to make resultant drawings more effective. Although this finding is based on a study of algorithms, it also applies in general graph visualization and evaluation.     

Predicting the labels of an unknown graph via adaptive exploration

Motivated by a problem of targeted advertising in social networks, we introduce a new model of online learning on labeled graphs where the graph is initially unknown and the algorithm is free to choose which vertex to predict next. For this learning model, we define an appropriate measure of regularity of a graph labeling called the merging degree. In general, the merging degree of a graph is small when its vertices can be partitioned into a few well-separated clusters within which labels are roughly constant. For the special case of binary labeled graphs, the merging degree is a more refined measure than the cutsize. After observing that natural nonadaptive exploration/prediction strategies, like depth-first with majority vote, do not behave satisfactorily on graphs with small merging degree, we introduce an efficiently implementable adaptive strategy whose cumulative loss is controlled by the merging degree. A matching lower bound shows that in the case of binary labels our analysis cannot be improved.     

Coherent time-varying graph drawing with multifocus+context interaction

We present a new approach for time-varying graph drawing that achieves both spatiotemporal coherence and multifocus+context visualization in a single framework. Our approach utilizes existing graph layout algorithms to produce the initial graph layout, and formulates the problem of generating coherent time-varying graph visualization with the focus+context capability as a specially tailored deformation optimization problem. We adopt the concept of the super graph to maintain spatiotemporal coherence and further balance the needs for aesthetic quality and dynamic stability when interacting with time-varying graphs through focus+context visualization. Our method is particularly useful for multifocus+context visualization of time-varying graphs where we can preserve the mental map by preventing nodes in the focus from undergoing abrupt changes in size and location in the time sequence. Experiments demonstrate that our method strikes a good balance between maintaining spatiotemporal coherence and accentuating visual foci, thus providing a more engaging viewing experience for the users.     

Graph matching using the interference of continuous-time quantum walks

We consider how continuous-time quantum walks can be used for graph matching. We focus in detail on both exact and inexact graph matching, and consider in depth the problem of measuring graph similarity. We commence by constructing an auxiliary graph, in which the two graphs to be matched are co-joined by a layer of indicator vertices (one for each potential correspondence between a pair of vertices). We simulate a continuous-time quantum walk in parallel on the two graphs. The layer of connecting indicator vertices in the auxiliary graph allow quantum interference to take place between the two walks. The interference amplitudes on the indicator vertices are determined by differences in the two walks, and can be used to calculate probabilities for matches between pairs of vertices from the graphs. By applying the Hungarian (Kuhn-Munkres) algorithm to these probabilities, we recover a correspondence mapping between the graphs. To calculate graph similarity, we combine these probabilities with edge-consistency information to give a consistency measure. Based on the consistency measure, we define two graph similarity measures, one of which requires correspondence matches while the second does not. We analyse our approach experimentally using synthetic and real-world graphs. This reveals that our method gives results that are intermediate between the most sophisticated iterative techniques available, and simpler less complex ones.     

Short Cycles Make W-hard Problems Hard: FPT Algorithms for W-hard Problems in Graphs with no Short Cycles

We show that several problems that are hard for various parameterized complexity classes on general graphs, become fixed parameter tractable on graphs with no small cycles. More specifically, we give fixed parameter tractable algorithms for Dominating Set, t -Vertex Cover (where we need to cover at least t edges) and several of their variants on graphs with girth at least five. These problems are known to be W[i]-hard for some i≥1 in general graphs. We also show that the Dominating Set problem is W[2]-hard for bipartite graphs and hence for triangle free graphs. In the case of Independent Set and several of its variants, we show these problems to be fixed parameter tractable even in triangle free graphs. In contrast, we show that the Dense Subgraph problem where one is interested in finding an induced subgraph on k vertices having at least l edges, parameterized by k, is W[1]-hard even on graphs with girth at least six. Finally, we give an O(log p) ratio approximation algorithm for the Dominating Set problem for graphs with girth at least 5, where p is the size of an optimum dominating set of the graph. This improves the previous O(log n) factor approximation algorithm for the problem, where n is the number of vertices of the input graph. A preliminary version of this paper appeared in the Proceedings of 10th Scandinavian Workshop on Algorithm Theory (SWAT), Lecture Notes in Computer Science, vol. 4059, pp. 304–315, 2006.     

Construction of the Algorithm Graph by Autotracing Method

An autotracing approach to the problem of the algorithm graph construction based on the possibility of overloading operators in the C++ language is suggested. The basic idea of the approach is to replace the standard double type by a special class number, which supports basic operations on numbers (arithmetic, input/output) and constructs the graph in a background mode. A class graph is responsible for general control of the graph construction process. Classes vector and matrix are introduced to support the construction of the graph for vector and matrix operations. The library of classes developed is a powerful and flexible tool for analysis of the algorithm graphs.     

Customizing a Fisheye View Algorithm to Preserve the Mental Map

Frequently, large knowledge bases are represented by graphs. Many visualization tools allow users or other applications to interact with and adjust the layouts of these graphs. One layout adjustment problem is that of showing more detail without eliding parts of the graph. Approaches based on a fisheye lens paradigm seem well suited to this task. However, many of these techniques are non-trivial to implement and their distortion techniques often cannot be altered to suit different graph layouts. When distorting a graph layout, it is often desirable to preserve various properties of the original graph in an adjusted view. Pertinent properties may include straightness of lines, graph topology, orthogonalities and proximities. However, it is normally not possible to preserve all of the original properties of the graph layout. The type of layout and its application should be considered when deciding which properties to preserve or distort. This paper describes a fisheye view algorithm which can be customized to suit various different graph layouts. In contrast to other methods, the user can select which properties of the original graph layout to preserve in an adjusted view. The technique is demonstrated through its application to visualizing structures in large software systems.     

Visual exploration of complex time-varying graphs

Quasi-trees, namely graphs with tree-like structure, appear in many application domains, including bioinformatics and computer networks. Our new SPF approach exploits the structure of these graphs with a two-level approach to drawing, where the graph is decomposed into a tree of biconnected components. The low-level biconnected components are drawn with a force-directed approach that uses a spanning tree skeleton as a starting point for the layout. The higher-level structure of the graph is a true tree with meta-nodes of variable size that contain each biconnected component. That tree is drawn with a new area-aware variant of a tree drawing algorithm that handles high-degree nodes gracefully, at the cost of allowing edge-node overlaps. SPF performs an order of magnitude faster than the best previous approaches, while producing drawings of commensurate or improved quality     

Maximum gap labelings of graphs

Given a graph, we define a base set to be a set of integers of size equal to the number of vertices in the graph. Given a graph and a base set, a labeling of the graph from the base set is an assignment of distinct integers from the base set to the vertices of the graph. The gap of an edge in a labeled graph is the absolute value of the difference between the labels of its endpoints. The gap of a labeled graph is the sum of the gaps of its edges.The maximum gap graph labeling problem takes as input a graph and a base set and maximizes the gap of the graph over all possible labelings from the base set. We show that this problem is NP-complete even when the base set is restricted to consecutive integers. We also show that this restricted case has polynomial time approximations that achieve a factor of 2/3 for trees, of 1/2 for bipartite graphs, and of 1/4 for general graphs, with a deterministic algorithm, while an expected factor of 1/3 for general graphs is achieved with a randomized algorithm. The case of general base sets is approximated within an expected factor of 1/16 for general graphs with a randomized polynomial time algorithm. We finally give a polynomial time algorithm that solves the maximum gap graph labeling problem for a graph that has bounded degree and bounded treewidth. The maximum graph labeling problem shows connections with the graceful tree conjecture.     

On Independent Vertex Sets in Subclasses of Apple-Free Graphs

In a finite undirected graph, an apple consists of a chordless cycle of length at least 4, and an additional vertex which is not in the cycle and sees exactly one of the cycle vertices. A graph is apple-free if it contains no induced subgraph isomorphic to an apple. Apple-free graphs are a common generalization of chordal graphs, claw-free graphs and cographs and occur in various papers. The Maximum Weight Independent Set (MWS) problem is efficiently solvable on chordal graphs, on cographs as well as on claw-free graphs. In this paper, we obtain partial results on some subclasses of apple-free graphs where our results show that the MWS problem is solvable in polynomial time. The main tool is a combination of clique separators with modular decomposition. Our algorithms are robust in the sense that there is no need to recognize whether the input graph is in the given graph class; the algorithm either solves the MWS problem correctly or detects that the input graph is not in the given class.