Drawing graphs with nonuniform nodes using potential fields

Graphs with nonuniform nodes arise naturally in many real-world applications. Although graph drawing has been a very active research in the computer science community during the past decade, most of the graph drawing algorithms developed thus far have been designed for graphs whose nodes are represented as single points. As a result, it is of importance to develop drawing methods for graphs whose nodes are of different sizes and shapes, in order to meet the need of real-world applications. To this end, a potential field approach, coupled with an idea commonly found in force-directed methods, is proposed in this paper for drawing graphs with nonuniform nodes in 2-D and 3-D. In our framework, nonuniform nodes are uniformly charged, while edges are modelled by springs. Using certain techniques developed in the field of potential-based path planning, we are able to find analytically tractable procedures for computing the repulsive force and torque of a node in the potential field induced by the remaining nodes. The crucial feature of our approach is that the rotation of every nonuniform node and the multiple edges between two nonuniform nodes are taken into account. In comparison with the existing algorithms found in the literature, our experimental results suggest this new approach to be promising, as drawings of good quality for a variety of moderate-sized graphs in 2-D and 3-D can be produced reasonably efficiently. That is, our approach is suitable for moderate-sized interactive graphs or larger-sized static graphs. Furthermore, to illustrate the usefulness of our new drawing method for graphs with zero-sized nodes, we give an application to the visualization of hierarchical clustered graphs, for which our method offers a very efficient solution.     

Complexity of homomorphisms to direct products of graphs

For a graph G, OALG asks whether or not an input graph H together with a partial map g:S→G, S⊆V(H), admits a homomorphism f:H→G such that f|_S=g. We show that for connected graphs G₁, G₂, OAL G₁×G₂ is in P if G₁ and G₂ are trees and NP-complete otherwise.     

On the complexity of digraph packings

Let be a fixed collection of digraphs. Given a digraph H, a -packing of H is a collection of vertex disjoint subgraphs of H, each isomorphic to a member of . For undirected graphs, Loebl and Poljak have completely characterized the complexity of deciding the existence of a perfect -packing, in the case that consists of two graphs one of which is a single edge on two vertices. We characterize -packing where consists of two digraphs one of which is a single arc on two vertices.     

Parameterized power domination complexity

The optimization problem of measuring all nodes in an electrical network by placing as few measurement units (PMUs) as possible is known as Power Dominating Set. Nodes can be measured indirectly according to Kirchhoff's law. We show that this problem can be solved in linear time for graphs of bounded treewidth and establish bounds on its parameterized complexity if the number of PMUs is the parameter.     

The complexity of changing colourings with bounded maximum degree

Let G be a graph, x,y∈V(G), and ?:V(G)→[k] a k-colouring of G such that ?(x)=?(y). If then the following question is NP-complete: Does there exist a k-colouring ?^′ of G such that ?^′(x)≠?^′(y)? Conversely, if then the problem is polynomial time.     

On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P

We show that computing the lexicographically first four-coloring for planar graphs is -hard. This result optimally improves upon a result of Khuller and Vazirani who prove this problem NP-hard, and conclude that it is not self-reducible in the sense of Schnorr, assuming P≠NP. We discuss this application to non-self-reducibility and provide a general related result. We also discuss when raising a problem's NP-hardness lower bound to -hardness can be valuable.     

The drawability problem for minimum weight triangulations

A graph is minimum weight drawable if it admits a straight-line drawing that is a minimum weight triangulation of the set of points representing the vertices of the graph. We study the problem of characterizing those graphs that are minimum weight drawable. Our contribution is twofold: We show that there exist infinitely many triangulations that are not minimum weight drawable. Furthermore, we present non-trivial classes of triangulations that are minimum weight drawable, along with corresponding linear time algorithms that take as input any graph from one of these classes and produce as output such a drawing. One consequence of our work is the construction of triangulations that are minimum weight drawable but not Delaunay drawable – that is, not drawable as a Delaunay triangulation.     

Complexity analysis of a decentralised graph colouring algorithm

Colouring a graph with its chromatic number of colours is known to be NP-hard. Identifying an algorithm in which decisions are made locally with no information about the graph's global structure is particularly challenging. In this article we analyse the complexity of a decentralised colouring algorithm that has recently been proposed for channel selection in wireless computer networks.     

On the complexity of graph self-assembly in accretive systems

We study the complexity of the Accretive Graph Assembly Problem (). An instance of consists of an edge-weighted graph G, a seed vertex in G, and a temperature τ. The goal is to determine if the graph G can be assembled by a sequence of vertex additions starting from the seed vertex. The edge weights model the forces of attraction and repulsion, and determine which vertices can be added to a partially assembled graph at the given temperature. A vertex can be added when the total weight to its already built neighbors in the graph is at least τ. The assembly process is sequential meaning that only one vertex can be added at a time. Our first result is that is NP-complete even on planar graphs with maximum degree 3 when edges have only two different types of weights. This resolves the complexity of in the sense that the problem is poly-time solvable when either the maximum degree is at most 2 or the number of distinct edge weights is one, and is NP-complete otherwise. Our second result is a dichotomy theorem that completely characterizes the complexity of on graphs with maximum degree 3 and two distinct weights: w _p and w _n . We give a simple system of linear constraints on w _p , w _n , and τ that determines whether the problem is NP-complete or is poly-time solvable. In the process of establishing this dichotomy, we give a poly-time algorithm to solve a non-trivial class of Finally, we consider the optimization version of where the goal is to assemble a largest-possible induced subgraph of the given input graph. We show that even on graphs that can be assembled and have maximum degree 3, it is NP-hard to assemble a (1/n ^1-ε)-fraction of the input graph for any here n denotes the number of vertices in G.     

Improved algorithm for finding next-to-shortest paths

We study the problem of finding the next-to-shortest paths in a weighted undirected graph. A next-to-shortest (u,v)-path is a shortest (u,v)-path amongst (u,v)-paths with length strictly greater than the length of the shortest (u,v)-path. The first polynomial algorithm for this problem was presented in [I. Krasikov, S.D. Noble, Finding next-to-shortest paths in a graph, Inform. Process. Lett. 92 (2004) 117-119]. We improve the upper bound from O(n³m) to O(n³).     

Finding next-to-shortest paths in a graph

We study the problem of finding the next-to-shortest paths in a graph. A next-to-shortest (u,v)-path is a shortest (u,v)-path amongst (u,v)-paths with length strictly greater than the length of the shortest (u,v)-path. In contrast to the situation in directed graphs, where the problem has been shown to be NP-hard, providing edges of length zero are allowed, we prove the somewhat surprising result that there is a polynomial time algorithm for the undirected version of the problem.     

Computing Graph Automorphism from Partial Solutions

It is known that, given two isomorphic graphs G and H, finding a pair of vertices (v _i ,w _j ) where v _i is mapped to w _j by an isomorphism from G to H is as hard as computing an isomorphism from G to H. In this paper, we prove a similar result for the Graph Automorphism problem. That is to say, we prove that, given a graph that has a non-trivial automorphism, finding a pair of vertices (v _i ,v _j ) where v _i is mapped to v _j by a non-trivial automorphism on the graph is as hard as computing a non-trivial automorphism on the graph.     

Finding optimal paths in MREP routing

Maximum Residual Energy Path (MREP) routing has been shown an effective routing scheme for energy conservation in battery powered wireless networks. Past studies on MREP routing are based on the assumption that the transmitting node consumes power, but the receiving node does not. This assumption is false if acknowledgment is required as occurs, for example, in some Bluetooth applications.If the receiving node does not consume power then the MREP routing problem for a single message is easily solvable in polynomial time using a simple Dijkstra-like algorithm. We further show in that when the receiving node does consume power the problem becomes NP-complete and is even impossible to approximate with an exponential approximation factor in polynomial time unless P=NP.     

On the approximability of two tree drawing conventions

We consider two aesthetic criteria for the visualization of rooted trees: inclusion and tip-over. Finding the minimum area layout according to either of these two standards is an NP-hard task, even when we restrict ourselves to binary trees.We provide a fully polynomial time approximation scheme for this problem. This result applies to any tree for tip-over layouts and to bounded degree trees in the case of the inclusion convention. We also prove that such restriction is necessary since, for unbounded degree trees, the inclusion problem is strongly NP-hard. Hence, neither a fully polynomial time approximation scheme nor a pseudopolynomial time algorithm exists, unless P=NP. Our technique, combined with the parallel algorithm by Metaxas et al. [Comput. Geom. 9 (1998) 145-158], also yields an NC fully parallel approximation scheme. This latter result holds for inclusion of binary trees and for the slicing floorplanning problem. Although this problem is in P, it is unknown whether it belongs to NC or not. All the above results also apply to other size functions of the drawing (e.g., the perimeter).     

A fixed-parameter tractable algorithm for matrix domination

Matrix domination is the NP-complete problem of determining whether a given {0,1} matrix contains a set of k non-zero entries that are in the same row or same column as all other non-zero entries. Using a kernelization and search tree approach, we show the problem to be fixed-parameter tractable with running time .     

Topological additive numbering of directed acyclic graphs

We propose to study a problem that arises naturally from both Topological Numbering of Directed Acyclic Graphs, and Additive Coloring (also known as Lucky Labeling). Let D be a digraph and f   a labeling of its vertices with positive integers; denote by S(v)$S(v)$ the sum of labels over all neighbors of each vertex v. The labeling f is called topological additive numbering   if S(u)<S(v)$S(u)<S(v)$ for each arc (u,v)$(u,v)$ of the digraph. The problem asks to find the minimum number k for which D   has a topological additive numbering with labels belonging to {1,…,k}$\{1,\dots ,k\}$, denoted by _ηt(D)${\eta }_t(D)$.     

两台流水机器协调分解调度问题

研究钢管加工流程中一类新型两台机器流水车间调度问题,工件在第一台机器上加工后被分解成多个子工件.对于最小化最大完成时间的情况,给出一个多项式时间的最优算法;对于最小化最大完成时间与惩罚费用之和的情况,给出一个拟多项式时间的动态规划算法;对于考虑生产前运输的最小化最大完成时间的情况,分析了问题的复杂性.证明了第一种情况的最优算法可作为后两种情况的2-近似算法.数值实验表明了算法的有效性.     

On the maximum acyclic subgraph problem under disjunctive constraints

Disjunctively constrained versions of classic problems in graph theory such as shortest paths, minimum spanning trees and maximum matchings were recently studied. In this article we introduce disjunctive constrained versions of the Maximum Acyclic Subgraph problem. Negative disjunctive constraints state that a certain pair of edges cannot be contained simultaneously in a feasible solution. Positive disjunctive constraints enforces that at least one arc for the underlying pair is in a feasible solution. It is convenient to represent these disjunctive constraints in terms of an undirected graph, called constraint graph, whose vertices correspond to the arcs of the original graph, and whose edges encode the disjunctive constraints. For the Maximum Acyclic Subgraph problem under Negative Disjunctive Constraints we develop 1/2-approximative algorithms that are polynomial for certain classes of constraint graphs. We also show that determining if a feasible solution exists for an instance of the Maximum Acyclic Subgraph problem under Positive Disjunctive Constraints is an NP-Complete problem.