Minimising the Number of Bends and Volume in 3-Dimensional Orthogonal Graph Drawings with a Diagonal Vertex Layout

A 3-dimensional orthogonal drawing of a graph with maximum degree at most 6, positions the vertices at grid-points in the 3-dimensional orthogonal grid, and routes edges along grid-lines such that edge routes only intersect at common end-vertices. Minimising the number of bends and the volume of 3-dimensional orthogonal drawings are established criteria for measuring the aesthetic quality of a given drawing. In this paper we present two algorithms for producing 3-dimensional orthogonal graph drawings with the vertices positioned along the main diagonal of a cube, so-called diagonal drawings. This vertex-layout strategy was introduced in the 3-BENDS algorithm of Eades et al. [Discrete Applied Math. 103:55–87, 2000]. We show that minimising the number of bends in a diagonal drawing of a given graph is NP-hard. Our first algorithm minimises the total number of bends for a fixed ordering of the vertices along the diagonal in linear time. Using two heuristics for determining this vertex-ordering we obtain upper bounds on the number of bends. Our second algorithm, which is a variation of the above-mentioned 3-BENDS algorithm, produces 3-bend drawings with n³+o(n³) volume, which is the best known upper bound for the volume of 3-dimensional orthogonal graph drawings with at most three bends per edge.     

Drawing graphs with right angle crossings

Cognitive experiments show that humans can read graph drawings in which all edge crossings are at right angles equally well as they can read planar drawings; they also show that the readability of a drawing is heavily affected by the number of bends along the edges. A graph visualization whose edges can only cross perpendicularly is called a RAC (Right Angle Crossing) drawing. This paper initiates the study of combinatorial and algorithmic questions related to the problem of computing RAC drawings with few bends per edge. Namely, we study the interplay between number of bends per edge and total number of edges in RAC drawings. We establish upper and lower bounds on these quantities by considering two classical graph drawing scenarios: The one where the algorithm can choose the combinatorial embedding of the input graph and the one where this embedding is fixed.     

Efficient Orthogonal Drawings of High Degree Graphs

Most of the work that appears in the two-dimensional orthogonal graph drawing literature deals with graphs whose maximum degree is four. In this paper we present an algorithm for orthogonal drawings of simple graphs with degree higher than four. Vertices are represented by rectangular boxes of perimeter less than twice the degree of the vertex. Our algorithm is based on creating groups / pairs of vertices of the graph. The orthogonal drawings produced by our algorithm have area at most (m-1) ( m / 2 +2) . Two important properties of our algorithm are that the drawings exhibit a small total number of bends (less than m ), and that there is at most one bend per edge. Received January 15, 1997; revised February 1, 1998.     

Orthogonal drawings and crossing numbers of the Kronecker product of two cycles

An orthogonal drawing of a graph is an embedding of the graph in the plane such that each edge is representable as a chain of alternately horizontal and vertical line segments. This style of drawing finds applications in areas such as optoelectronic systems, information visualization and VLSI circuits. We present orthogonal drawings of the Kronecker product of two cycles around vertex partitions of the graph into grids. In the process, we derive upper bounds on the crossing number of the graph. The resulting upper bounds are within a constant multiple of the lower bounds. Unlike the Cartesian product that is amenable to an inductive treatment, the Kronecker product entails a case-to-case analysis since the results depend heavily on the parameters corresponding to the lengths of the two cycles.     

Branch and bound for the cutwidth minimization problem

The cutwidth minimization problem consists of finding a linear arrangement of the vertices of a graph where the maximum number of cuts between the edges of the graph and a line separating consecutive vertices is minimized. We first review previous approaches for special classes of graphs, followed by lower bounds and then a linear integer formulation for the general problem. We then propose a branch-and-bound algorithm based on different lower bounds on the cutwidth of partial solutions. Additionally, we introduce a Greedy Randomized Adaptive Search Procedure (GRASP) heuristic to obtain good initial solutions. The combination of the branch-and-bound and GRASP methods results in optimal solutions or a reduced relative gap (difference between upper and lower bounds) on the instances tested. Empirical results with a collection of previously reported instances indicate that the proposed algorithm is able to solve all the small instances (up to 32 vertices) as well as some of the large instances tested (up to 158 vertices) using less than 30 minutes of CPU time. We compare the results of our method with previous lower bounds, and with the best previous linear integer formulation solved using Cplex. Both comparisons favor the proposed procedure.     

Drawing planar graphs using the canonical ordering

We introduce a new method to optimize the required area, minimum angle, and number of bends of planar graph drawings on a grid. The main tool is a new type of ordering on the vertices and faces of triconnected planar graphs. Using this method linear-time-and-space algorithms can be designed for many graph-drawing problems. Our main results are as follows:

Every triconnected planar graphG admits a planar convex grid drawing with straight lines on a (2n?4)×(n?2) grid, wheren is the number of vertices.

Every triconnected planar graph with maximum degree 4 admits a planar orthogonal grid drawing on ann×n grid with at most [3n/2]+4 bends, and ifn>6, then every edge has at most two bends.

Every planar graph with maximum degree 3 admits a planar orthogonal grid drawing with at most [n/2]+1 bends on an [n/2]×[n/2] grid.

Every triconnected planar graphG admits a planar polyline grid drawing on a (2n?6)×(3n?9) grid with minimum angle larger than 2/d radians and at most 5n?15 bends, withd the maximum degree.

These results give in some cases considerable improvements over previous results, and give new bounds in other cases. Several other results, e.g., concerning visibility representations, are included.     

Bounded-Degree Independent Sets in Planar Graphs

An independent set of a graph is a set of vertices without edges between them. Every planar graph has an independent set of size at least (1/4)n and there are planar graphs for which any independent set has size at most (1/4)n. In this paper similar bounds are provided for the problem of bounded-degree independent set, i.e., an independent set where additionally all vertices have degree less than a pre-specified bound D. Our upper and lower bounds match (up to a small constant) for D 16.     

Three-dimensional graph drawing

Graph drawing research has been mostly oriented toward two-dimensional drawings. This paper describes an investigation of fundamental aspects of three-dimensional graph drawing. In particular we give three results concerning the space required for three-dimensional drawings. We show how to produce a grid drawing of an arbitraryn-vertex graph with all vertices located at integer grid points, in ann×2n×2n grid, such that no pair of edges cross. This grid size is optimal to within a constant. We also show how to convert an orthogonal two-dimensional drawing in anH×V integer grid to a three-dimensional drawing with volume. Using this technique we show, for example, that three-dimensional drawings of binary trees can be computed with volume . We give an algorithm for producing drawings of rooted trees in which thez-coordinate of a node represents the depth of the node in the tree; our algorithm minimizes thefootprint of the drawing, that is, the size of the projection in thexy plane. Finally, we list significant unsolved problems in algorithms for three-dimensional graph drawing. This work was performed as part of the Information Visualization Group(IVG) at the University of Newcastle. The IVG is supported in part by IBM Toronto Laboratory.     

Dynamic monopolies and feedback vertex sets in hexagonal grids

In a majority conversion process, the vertices of a graph can be in one of the two states, colored or uncolored, and these states are dynamically updated so that a vertex becomes colored at a certain time period if at least half of its neighbors were in the colored state in the previous time period. A dynamic monopoly is a set of vertices in a graph that when initially colored will eventually cause all vertices in the graph to become colored. This paper establishes a connection between dynamic monopolies and the well-known feedback vertex sets which are sets of vertices whose removal results in an acyclic graph. More specifically, we show that dynamic monopolies and feedback vertex sets are equivalent in graphs wherein all vertices have degree 2 or 3. We use this equivalence to provide exact values for the minimum size of dynamic monopolies of planar hexagonal grids, as well as upper and lower bounds on the minimum size of dynamic monopolies of cylindrical and toroidal hexagonal grids. For these last two topologies, the respective upper and lower bounds differ by at most one.     

How to draw free trees inside bounded rectilinear polygons

Drawing graphs on a 2D grid with prescribed size is NP-complete, even if we restrict ourselves to planar orthogonal grid drawings of trees. In this paper, we introduce a new algorithm for polyline drawing of free trees on 2D grids which are bounded by rectilinear polygons. Our algorithm uses straight skeleton and simulated annealing and aims to distribute the vertices of the given trees uniformly on the given bounded grids. Our experimental results show that our algorithm is relatively successful to achieve uniform distribution of the nodes of the given trees. To our knowledge, this paper is the first attempt to develop algorithms that draw trees on restricted 2D grids which are bounded by simple rectilinear polygons.     

On simultaneous straight-line grid embedding of a planar graph and its dual

Simultaneous representations of planar graphs and their duals normally require that the dual vertices to be placed inside their corresponding primal faces, and the edges of the dual graph to cross only their corresponding primal edges. Erten and Kobourov [C. Erten, S.G. Kobourov, Simultaneous embedding of a planar graph and its dual on the grid, Theory Computer Systems 38 (2005) 313-327] provided a linear time algorithm on simultaneous straight-line grid embedding of a 3-connected planar graph and its dual such that all the vertices are placed on grid points and each edge is drawn as one straight-line segment except for one which is drawn using two segments. Their drawing size is (2n−2)×(2n−2), where n is the total number of vertices in the graph and its dual. They raised an open question on whether there is a large class of planar graphs that allows this simultaneous straight-line grid embedding on a smaller grid. We answer this open question by giving a linear time simultaneous straight-line grid embedding algorithm for a 3-connected planar graph and its dual on a grid of size (n−1)×n.     

Output-Sensitive Reporting of Disjoint Paths

A k -path query on a graph consists of computing k vertex-disjoint paths between two given vertices of the graph, whenever they exist. In this paper we study the problem of performing k -path queries, with , in a graph G with n vertices. We denote with the total length of the reported paths. For , we present an optimal data structure for G that uses O(n) space and executes k -path queries in output-sensitive time. For triconnected planar graphs, our results make use of a new combinatorial structure that plays the same role as bipolar (st ) orientations for biconnected planar graphs. This combinatorial structure also yields an alternative construction of convex grid drawings of triconnected planar graphs. Received August 24, 1996; revised April 8, 1997.     

Simultaneous Embedding of a Planar Graph and Its Dual on the Grid

Traditional representations of graphs and their duals suggest that the dual vertices should be placed inside their corresponding primal faces, and the edges of the dual graph should only cross their corresponding primal edges. We consider the problem of simultaneously embedding a planar graph and its dual on a small integer grid such that the edges are drawn as straight-line segments and the only crossings are between primal--dual pairs of edges. We provide an O(n) time algorithm that simultaneously embeds a 3-connected planar graph and its dual on a (2n - 2) × (2n - 2) integer grid, where n is the total number of vertices in the graph and its dual. All the edges are drawn as straight-line segments except for one edge on the outer face, which is drawn using two segments.     

Drawing Planar Graphs Symmetrically, III: Oneconnected Planar Graphs

Symmetry is one of the most important aesthetic criteria in graph drawing because it reveals structure in the graph. This paper discusses symmetric drawings of oneconnected planar graphs. More specifically, we discuss planar (geometric) automorphisms, that is, automorphisms of a graph G that can be represented as symmetries of a planar drawing of G. Finding planar automorphisms is the first and most difficult step in constructing planar symmetric drawings of graphs. The problem of determining whether a given graph has a nontrivial geometric automorphism is NP-complete for general graphs. The two previous papers in this series have discussed the problem of drawing planar graphs with a maximum number of symmetries, for the restricted cases where the graph is triconnected and biconnected. This paper extends the previous results to cover planar graphs that are oneconnected. We present a linear time algorithm for drawing oneconnected planar graphs with a maximum number of symmetries.     

Optimal Polygonal Representation of Planar Graphs

In this paper, we consider the problem of representing planar graphs by polygons whose sides touch. We show that at least six sides per polygon are necessary by constructing a class of planar graphs that cannot be represented by pentagons. We also show that the lower bound of six sides is matched by an upper bound of six sides with a linear-time algorithm for representing any planar graph by touching hexagons. Moreover, our algorithm produces convex polygons with edges having at most three slopes and with all vertices lying on an O(n)×O(n) grid.     

On the Incompressibility of Monotone DNFs

We prove optimal lower bounds for multilinear circuits and for monotone circuits with bounded depth. These lower bounds state that, in order to compute certain functions, these circuits need exactly as many OR gates as the respective DNFs. The proofs exploit a property of the functions that is based solely on prime implicant structure. Due to this feature, the lower bounds proved also hold for approximations of the considered functions that are similar to slice functions. Known lower bound arguments cannot handle these kinds of approximations. In order to show limitations of our approach, we prove that cliques of size n - 1 can be detected in a graph with n vertices by monotone formulas with O(log n) OR gates. Our lower bound for multilinear circuits improves a lower bound due to Borodin, Razborov and Smolensky for nondeterministic read-once branching programs computing the clique function.     

Two models of two-dimensional bandwidth problems

The two-dimensional bandwidth problem is to embed a graph G into an n×n grid in the plane such that the maximum distance between adjacent vertices is as small as possible. Here, the “distance” has two different meanings: the L₁-norm distance and L_∞-norm distance. So we have two models of two-dimensional bandwidth problem. This paper investigates the basic properties and relations of these two models. Some lower bounds, upper bounds, and exact results are presented.     

Parameterized complexity of firefighting

The Firefighter problem is to place firefighters on the vertices of a graph to prevent a fire with known starting point from lighting up the entire graph. In each time step, a firefighter may be placed on an unburned vertex, permanently protecting it, and the fire spreads to all neighboring unprotected vertices of burning vertices. The goal is to let as few vertices burn as possible. In this paper, we consider a generalization of this problem, where at each time step b?1$b?1$ firefighters can be deployed. Our results answer several open questions raised by Cai et al. [8]. We show that this problem is W[1]-hard when parameterized by the number of saved vertices, protected vertices, and burned vertices. We also investigate several combined parameterizations for which the problem is fixed-parameter tractable. Some of our algorithms improve on previously known algorithms. We also establish lower bounds to polynomial kernelization.     

一些新的Hamilton图的必要条件

寻求Hamilton图的适当的特征刻画是图论的一个重大未解决问题,根据图的结构特征,设计了图的顶点的分层方法,研究了Hamilton图中层与层间对外顶点数和对外边数应该满足的关系,分析了Hamilton图中每层顶点数与每层对外项点数的关系,探讨了图与其Hamilton演化图的Hamilton性关系,最后得到一些新的Hamilton图的必要条件。所获得的新的Hamilton图的必要条件实用性强,使用方便,能判断一些原必要条件不能判断的非Hamilton图。     

On the Parameterized Complexity of Layered Graph Drawing

We consider graph drawings in which vertices are assigned to layers and edges are drawn as straight line-segments between vertices on adjacent layers. We prove that graphs admitting crossing-free h-layer drawings (for fixed h) have bounded pathwidth. We then use a path decomposition as the basis for a linear-time algorithm to decide if a graph has a crossing-free h-layer drawing (for fixed h). This algorithm is extended to solve related problems, including allowing at most k crossings, or removing at most r edges to leave a crossing-free drawing (for fixed k or r). If the number of crossings or deleted edges is a non-fixed parameter then these problems are NP-complete. For each setting, we can also permit downward drawings of directed graphs and drawings in which edges may span multiple layers, in which case either the total span or the maximum span of edges can be minimized. In contrast to the Sugiyama method for layered graph drawing, our algorithms do not assume a preassignment of the vertices to layers. Research initiated at the International Workshop on Fixed Parameter Tractability in Graph Drawing, Bellairs Research Institute of McGill University, Holetown, Barbados, Feb. 9–16, 2001, organized by S. Whitesides. Research of Canada-based authors is supported by NSERC; research of Quebec-based authors is also supported by a grant from FCAR. Research of D.R. Wood completed while visiting McGill University. Research of G. Liotta supported by CNR and MURST.