On Triangulating Planar Graphs under the Four-Connectivity Constraint

Triangulation of planar graphs under constraints is a fundamental problem in the representation of objects. Related keywords are graph augmentation from the field of graph algorithms and mesh generation from the field of computational geometry. We consider the triangulation problem for planar graphs under the constraint to satisfy 4-connectivity. A 4-connected planar graph has no separating triangles, i.e., cycles of length 3 which are not a face. We show that triangulating embedded planar graphs without introducing new separating triangles can be solved in linear time and space. If the initial graph had no separating triangle, the resulting triangulation is 4-connected. If the planar graph is not embedded, then deciding whether there exists an embedding with at most k separating triangles is NP-complete. For biconnected graphs a linear-time approximation which produces an embedding with at most twice the optimal number is presented. With this algorithm we can check in linear time whether a biconnected planar graph can be made 4-connected while maintaining planarity. Several related remarks and results are included. Received August 1, 1995; revised July 8, 1996, and August 23, 1996.     

Property Testing in Bounded Degree Graphs

Abstract. We further develop the study of testing graph properties as initiated by Goldreich, Goldwasser and Ron. Loosely speaking, given an oracle access to a graph, we wish to distinguish the case when the graph has a pre-determined property from the case when it is ``far' from having this property. Whereas they view graphs as represented by their adjacency matrix and measure the distance between graphs as a fraction of all possible vertex pairs, we view graphs as represented by bounded-length incidence lists and measure the distance between graphs as a fraction of the maximum possible number of edges. Thus, while the previous model is most appropriate for the study of dense graphs, our model is most appropriate for the study of bounded-degree graphs. In particular, we present randomized algorithms for testing whether an unknown bounded-degree graph is connected, k -connected (for k>1 ), cycle-free and Eulerian. Our algorithms work in time polynomial in 1/ɛ , always accept the graph when it has the tested property, and reject with high probability if the graph is ɛ -far from having the property. For example, the 2-connectivity algorithm rejects (with high probability) any N -vertex d -degree graph for which more than ɛ dN edges need to be added in order to make the graph 2-edge-connected. In addition we prove lower bounds of Ω(\sqrt N ) on the query complexity of testing algorithms for the bipartite and expander properties.     

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.     

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.     

A New Approximation Algorithm for Finding Heavy Planar Subgraphs

Abstract. We provide the first nontrivial approximation algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH, the NP-hard problem of finding a heaviest planar subgraph in an edge-weighted graph G . This problem has applications in circuit layout, facility layout, and graph drawing. No previous algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH had a performance ratio exceeding 1/3 , which is obtained by any algorithm that produces a maximum weight spanning tree in G . Based on the Berman—Ramaiyer Steiner tree algorithm, the new algorithm has performance ratio at least 1/3+1/72 and at most 5/12 . We also show that if G is complete and its edge weights satisfy the triangle inequality, then the performance ratio is at least 3/8 . Furthermore, we derive the first nontrivial performance ratio (7/12 instead of 1/2 ) for the NP-hard SC MAXIMUM WEIGHT OUTERPLANAR SUBGRAPH problem.     

Planar Polyline Drawings via Graph Transformations

We study the problem of transforming plane triangulations into irreducible triangulations, which are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. Our linear time transformation reveals important relations between the minimum Schnyder’s realizers of plane triangulations (Bonichon et al., Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 2607, pp. 499–510, Springer, Berlin, 2003; Research Report RR-1279-02, LaBRI, University of Bordeaux, France; Brehm, Diploma thesis, FB Mathematik und Informatik, Freie Universität Berlin, 2000) and the transversal structures of irreducible triangulations (Fusy, Proceedings of 13th International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 3843, pp. 177–188, Springer, Berlin, 2005; He, SIAM J. Comput. 22:1218–1226, 1993). The transformation morphs a 3-connected plane graph into an internally 4-connected plane graph. Therefore some of the graph algorithms designed specifically for 4-connected plane graphs can be applied to 3-connected plane graphs indirectly. As an example of such applications, we present a linear time algorithm that produces a planar polyline drawing for a plane graph with n vertices in a grid of size bounded by W×H, where $W\leq\lfloor\frac{2n-2}{3}\rfloorWe study the problem of transforming plane triangulations into irreducible triangulations, which are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. Our linear time transformation reveals important relations between the minimum Schnyder’s realizers of plane triangulations (Bonichon et al., Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 2607, pp. 499–510, Springer, Berlin, 2003; Research Report RR-1279-02, LaBRI, University of Bordeaux, France; Brehm, Diploma thesis, FB Mathematik und Informatik, Freie Universit?t Berlin, 2000) and the transversal structures of irreducible triangulations (Fusy, Proceedings of 13th International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 3843, pp. 177–188, Springer, Berlin, 2005; He, SIAM J. Comput. 22:1218–1226, 1993). The transformation morphs a 3-connected plane graph into an internally 4-connected plane graph. Therefore some of the graph algorithms designed specifically for 4-connected plane graphs can be applied to 3-connected plane graphs indirectly. As an example of such applications, we present a linear time algorithm that produces a planar polyline drawing for a plane graph with n vertices in a grid of size bounded by W×H, where W ￡ ?\frac2n-23?W\leq\lfloor\frac{2n-2}{3}\rfloor , and W+H ￡ ?\frac4n-43?W+H\leq\lfloor \frac{4n-4}{3}\rfloor . It uses at most ?\frac2n-53?\lfloor\frac{2n-5}{3}\rfloor bends, and each edge uses at most one bend. Our algorithm is area optimal. Compared with the existing area optimal polyline drawing algorithm proposed in Bonichon et al. (Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 2573, pp. 35–46, Springer, Berlin, 2002), our algorithm uses a smaller number of bends. Their bend bound is (n−2).     

Mental map preserving graph drawing using simulated annealing

Visualizing graphs has been studied extensively in the community of graph drawing and information visualization over the years. In some applications, the user is required to interact with a graph by making slight changes to the underlying graph structure. To visualize graphs in such an interactive environment, it is desirable that the differences between the displays of the original and the modified graphs be kept minimal, allowing the user to comprehend the changes in the graph structure faster. As the mental map concept refers to the presentation of a person’s mind while exploring visual information, the better the mental map is preserved, the easier the structure change of a graph is understood. It is somewhat surprising that preserving the user’s mental map has largely been ignored in the graph drawing community in the past. We propose an effective mental-map-preserving graph drawing algorithm for straight-line drawings of general undirected graphs based on the simulated-annealing technique. Our experimental results and questionnaire analysis suggest this new approach to be promising.     

A Functional Approach to External Graph Algorithms

Abstract. We present a new approach for designing external graph algorithms and use it to design simple, deterministic and randomized external algorithms for computing connected components, minimum spanning forests, bottleneck minimum spanning forests, maximal independent sets (randomized only), and maximal matchings in undirected graphs. Our I/ O bounds compete with those of previous approaches. We also introduce a semi-external model, in which the vertex set but not the edge set of a graph fits in main memory. In this model we give an improved connected components algorithm, using new results for external grouping and sorting with duplicates. Unlike previous approaches, ours is purely functional—without side effects—and is thus amenable to standard checkpointing and programming language optimization techniques. This is an important practical consideration for applications that may take hours to run.     

An Algorithm for Enumerating All Spanning Trees of a Directed Graph

We present an O(NV + V ³ ) time algorithm for enumerating all spanning trees of a directed graph. This improves the previous best known bound of O(NE + V+E) [1] when V ² =o(N) , which will be true for most graphs. Here, N refers to the number of spanning trees of a graph having V vertices and E edges. The algorithm is based on the technique of obtaining one spanning tree from another by a series of edge swaps. This result complements the result in the companion paper [3] which enumerates all spanning trees in an undirected graph in O(N+V+E) time. Received September 11, 1997; revised March 6, 1998.     

A Minimal Line Property Preserving Representation of Line Images

In line image understanding a minimal line property preserving (MLPP) graph of the image compliments the structural information in geometric graph representations like the run graph. With such a graph and its dual it is possible to efficiently detect topological features like loops and holes and to make use of relations like containment. We present a new rule based method on dual graph contraction for transforming the run graph and its dual into MLPP graphs. A parallel O(log(longest curve)) algorithm is presented and results given. Received: May 28, 1998; revised November 17, 1998     

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.     

A Generalization of AT-Free Graphs and a Generic Algorithm for Solving Triangulation Problems

Abstract. A subset A of the vertices of a graph G is an asteroidal set if for each vertex a ∈ A a connected component of G-N[a] exists containing A\backslash{a} . An asteroidal set of cardinality three is called asteriodal triple and graphs without an asteriodal triple are called AT-free . The maximum cardinality of an asteroidal set of G , denoted by \an(G) , is said to be the asteriodal number of G . We present a scheme for designing algorithms for triangulation problems on graphs. As a consequence, we obtain algorithms to compute graph parameters such as treewidth, minimum fill-in and vertex ranking number. The running time of these algorithms is a polynomial (of degree asteriodal number plus a small constant) in the number of vertices and the number of minimal separators of the input graph.     

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.     

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.     

A Visualization Framework and User Studies for Overloaded Orthogonal Drawings

Overloaded orthogonal drawing (OOD) is a recent graph visualization style specifically conceived for directed graphs. It merges the advantages of some popular drawing conventions like layered drawings and orthogonal drawings, and provides additional support for some common analysis tasks. We present a visualization framework called DAGView, which implements algorithms and graphical features for the OOD style. Besides the algorithm for acyclic digraphs, the DAGView framework implements extensions to visualize both digraphs with cycles and undirected graphs, with the additional possibility of taking into account user preferences and constraints. It also supports an interactive visualization of clustered digraphs, based on the use of strongly connected components. Moreover, we describe an experimental user study, aimed to investigate the usability of OOD within the DAGView framework. The results of our study suggest that OOD can be effectively exploited to perform some basic tasks of analysis in a faster and more accurate way when compared to other drawing styles for directed graphs.     

A new force-directed graph drawing method based on edge–edge repulsion

The conventional force-directed methods for drawing undirected graphs are based on either vertex–vertex repulsion or vertex–edge repulsion. In this paper, we propose a new force-directed method based on edge–edge repulsion to draw graphs. In our framework, edges are modelled as charged springs, and a final drawing can be generated by adjusting positions of vertices according to spring forces and the repulsive forces, derived from potential fields, among edges. Different from the previous methods, our new framework has the advantage of overcoming the problem of zero angular resolution, guaranteeing the absence of any overlapping of edges incident to the common vertex. Given graph layouts probably generated by previous algorithms as the inputs to our algorithm, experimental results reveal that our approach produces promising drawings not only preserving the original properties of a high degree of symmetry and uniform edge length, but also preventing zero angular resolution and usually having larger average angular resolution. However, it should be noted that exhibiting a higher degree of symmetry and larger average angular resolution does not come without a price, as the new approach might result in the increase in undesirable overlapping of vertices as some of our experimental results indicate. To ease the problem of node overlapping, we also consider a hybrid approach which takes into account both edge–edge and vertex–vertex repulsive forces in drawing a graph.     

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.     

Aesthetics-based Graph Layout for Human Consumption

Automatic graph layout is an important and long-studied problem. The basic straight-edge graph layout problem is to find spatial positions for the nodes of an input graph that maximize some measure of desirability. When graph layout is intended for human consumption, we call this measure of desirability an aesthetic. We seek an algorithm that produces graph layouts of high aesthetic quality not only for general graphs, but also for specific classes of graphs, such as trees and directed acyclic graphs. The Aesthetic Graph Layout (AGLO) approach described in this paper models graph layout as a multiobjective optimization problem, where the value of a layout is determined by multiple user-controlled layout aesthetics. The current AGLO algorithm combines the power and flexibility of the simulated annealing approach of Davidson and Harel (1989) with the relative speed of the method of Fruchterman and Reingold (1991). In addition, it is more general, and incorporates several new layout aesthetics to support new layout styles. Using these aesthetics, we are able to produce pleasing displays for graphs on which these other methods flounder.     

Maximum planar subgraphs and nice embeddings: Practical layout tools

In automatic graph drawing a given graph has to be laid out in the plane, usually according to a number of topological and aesthetic constraints. Nice drawings for sparse nonplanar graphs can be achieved by determining a maximum planar subgraph and augmenting an embedding of this graph. This approach appears to be of limited value in practice, because the maximum planar subgraph problem is NP-hard.We attack the maximum planar subgraph problem with a branch-and-cut technique which gives us quite good, and in many cases provably optimum, solutions for sparse graphs and very dense graphs. In the theoretical part of the paper, the polytope of all planar subgraphs of a graphG is defined and studied. All subgraphs of a graphG, which are subdivisions ofK ₅ orK _3,3, turn out to define facets of this polytope. For cliques contained inG, the Euler inequalities turn out to be facet-defining for the planar subgraph polytope. Moreover, we introduce the subdivision inequalities,V _2k inequalities, and the flower inequalities, all of which are facet-defining for the polytope. Furthermore, the composition of inequalities by 2-sums is investigated.We also present computational experience with a branch-and-cut algorithm for the above problem. Our approach is based on an algorithm which searches for forbidden substructures in a graph that contains a subdivision ofK ₅ orK _3,3. These structures give us inequalities which are used as cutting planes.Finally, we try to convince the reader that the computation of maximum planar subgraphs is indeed a practical tool for finding nice embeddings by applying this method to graphs taken from the literature.     

Maximum Induced Matchings for Chordal Graphs in Linear Time

The Maximum Induced Matching (MIM) Problem asks for a largest set of pairwise vertex-disjoint edges in a graph which are pairwise of distance at least two. It is well-known that the MIM problem is NP-complete even on particular bipartite graphs and on line graphs. On the other hand, it is solvable in polynomial time for various classes of graphs (such as chordal, weakly chordal, interval, circular-arc graphs and others) since the MIM problem on graph G corresponds to the Maximum Independent Set problem on the square G ^*=L(G)² of the line graph L(G) of G, and in some cases, G ^* is in the same graph class; for example, for chordal graphs G, G ^* is chordal. The construction of G ^*, however, requires time, where m is the number of edges in G. Is has been an open problem whether there is a linear-time algorithm for the MIM problem on chordal graphs. We give such an algorithm which is based on perfect elimination order and LexBFS.