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.     

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.     

An Algorithm for Straight-Line Drawing of Planar Graphs

We present a new algorithm for drawing planar graphs on the plane. It can be viewed as a generalization of the algorithm of Chrobak and Payne, which, in turn, is based on an algorithm by de Fraysseix, Pach, and Pollack. Our algorithm improves the previous ones in that it does not require a preliminary triangulation step; triangulation proves problematic in drawing graphs ``nicely,' as it has the tendency to ruin the structure of the input graph. The new algorithm retains the positive features of the previous algorithms: it embeds a biconnected graph of n vertices on a grid of size (2n-4) x (n-2) in linear time. We have implemented the algorithm as part of a software system for drawing graphs nicely. Received September 21, 1995; revised March 15, 1996.     

A Linear-Time Algorithm for Star-Shaped Drawings of Planar Graphs with the Minimum Number of Concave Corners

A star-shaped drawing of a graph is a straight-line drawing such that each inner facial cycle is drawn as a star-shaped polygon, and the outer facial cycle is drawn as a convex polygon. In this paper, we consider the problem of finding a star-shaped drawing of a biconnected planar graph with the minimum number of concave corners. We first show new structural properties of planar graphs to derive a lower bound on the number of concave corners. Based on the lower bound, we prove that the problem can be solved in linear time by presenting a linear-time algorithm for finding a best plane embedding of a biconnected planar graph with the minimum number of concave corners. This is in spite of the fact that a biconnected planar graph may have an exponential number of different plane embeddings.     

Straight-Line Drawing Algorithms for Hierarchical Graphs and Clustered Graphs

Hierarchical graphs and clustered graphs are useful non-classical graph models for structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures. Both have applications in CASE tools, software visualization and VLSI design. Drawing algorithms for hierarchical graphs have been well investigated. However, the problem of planar straight-line representation has not been solved completely. In this paper we answer the question: does every planar hierarchical graph admit a planar straight-line hierarchical drawing? We present an algorithm that constructs such drawings in linear time. Also, we answer a basic question for clustered graphs, that is, does every planar clustered graph admit a planar straight-line drawing with clusters drawn as convex polygons? We provide a method for such drawings based on our algorithm for hierarchical graphs.     

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.     

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     

Inserting an Edge into a Planar Graph

Computing a crossing minimum drawing of a given planar graph G augmented by an additional edge e where all crossings involve e, has been a long standing open problem in graph drawing. Alternatively, the problem can be stated as finding a combinatorial embedding of a planar graph G where the given edge e can be inserted with the minimum number of crossings. Many problems concerned with the optimization over the set of all combinatorial embeddings of a planar graph turned out to be NP-hard. Surprisingly, we found a conceptually simple linear time algorithm based on SPQR-trees, that is able to find a solution with the minimum number of crossings.     

A Linear Time Algorithm for the Arc Disjoint Menger Problem in Planar Directed Graphs

Given a graph G=(V,E) and two vertices s,t ∈ V , s\neq t , the Menger problem is to find a maximum number of disjoint paths connecting s and t . Depending on whether the input graph is directed or not, and what kind of disjointness criterion is demanded, this general formulation is specialized to the directed or undirected vertex, and the edge or arc disjoint Menger problem, respectively. For planar graphs the edge disjoint Menger problem has been solved to optimality [W2], while the fastest algorithm for the arc disjoint version is Weihe's general maximum flow algorithm for planar networks [W1], which has running time \bf O (|V| log |V|) . Here we present a linear time, i.e., asymptotically optimal, algorithm for the arc disjoint version in planar directed graphs. Received August 1997; revised January 1999.     

用遗传算法画无向图

本文提出了一个新的画一般无向图的遗传算法.以前的无向图画图算法将顶点数较多且无弦的圈画成了凹多边形,为了克服这一缺点,本文的遗传算法设计了全新的变异算子--单点邻域变异,并在适应度函数中增加用于产生对称画法的分量,可将这种图画成凸多边形.新算法的优点是方法简单,易于实现,画出的图形美观,其灵活之处在于准则的权重可以改变.实验结果表明,在相同条件下,本文算法画出的图形要比标准遗传算法画出的图形美观.     

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.     

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.     

基于搜索树的平面图支配集算法

许多来自工业应用的优化问题都是NP难问题。确定参数可解FPT作为处理这类问题的另外一种思路,在最近的10多年中受到了广泛的关注。支配集问题是图论中最重要的NP完全的组合优化问题之一,即使对于FPT体系而言,一般图中的支配集问题属于W[2]完全的,意味着不可能设计出复杂度为f(k)no(1)的算法。在本文中,我们考虑在给定的平面图G=(V,E)中参数化支配集问题,给定参数k,看是否存在大小为k的顶点集合支配图中的其他顶点,当把问题限定在平面图上,这个问题属于确定参数可解。本文给出了基于两组归约规则的搜索树算法,通过使用规约技术化简实例,构造搜索树,得到了复杂度为O(8kn)的算法,同时通过相关实验结果显示了归约规则对算法的作用。     

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.     

Exponential Speedup of Fixed-Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors

We present a fixed-parameter algorithm that constructively solves the $k$-dominating set problem on any class of graphs excluding a single-crossing graph (a graph that can be drawn in the plane with at most one crossing) as a minor in $O(4^{9.55\sqrt{k}}n^{O(1)})$ time. Examples of such graph classes are the $K_{3,3}$-minor-free graphs and the $K_{5}$-minor-free graphs. As a consequence, we extend our results to several other problems such as vertex cover, edge dominating set, independent set, clique-transversal set, kernels in digraphs, feedback vertex set, and a collection of vertex-removal problems. Our work generalizes and extends the recent results of exponential speedup in designing fixed-parameter algorithms on planar graphs due to Alber et al. to other (nonplanar) classes of graphs.     

Testing Planarity of Geometric Automorphisms in Linear Time

It is a well-known result that testing a graph for planarity and, in the affirmative case, computing a planar embedding can be done in linear time. In this paper, we show that the same holds if additionally we require that the produced drawing be symmetric with respect to a given automorphism of the graph. This problem arises naturally in the area of automatic graph drawing, where symmetric and planar drawings are desired whenever possible. An extended abstract of this paper has been published in the proceedings of ISAAC 2002 (Lecture Notes in Computer Science, vol. 2518, pp. 563–574, 2002). The first author is supported by the Marie Curie Research Training Network ADONET 504438 funded by the EU. This paper was partially written when he was visiting the University of Sydney. The second author was supported by a grant from the Australian Research Council. National ICT Australia is funded by the Australian Government’s Backing Australia’s Ability initiative, in part through the Australian Research Council.     

Small Area Drawings of Outerplanar Graphs

We show three linear-time algorithms for constructing planar straight-line grid drawings of outerplanar graphs. The first and the second algorithm are for balanced outerplanar graphs. Both require linear area. The drawings produced by the first algorithm are not outerplanar while those produced by the second algorithm are. On the other hand, the first algorithm constructs drawings with better angular resolution. The third algorithm constructs outerplanar drawings of general outerplanar graphs with O(n ^1.48) area. Further, we study the interplay between the area requirements of the drawings of an outerplanar graph and the area requirements of a special class of drawings of its dual tree. Work partially supported by MUR under Project MAINSTREAM Algorithms for Massive Information Structures and Data Streams.     

Fast 3-coloring Triangle-Free Planar Graphs

Although deciding whether the vertices of a planar graph can be colored with three colors is NP-hard, the widely known Grötzsch’s theorem states that every triangle-free planar graph is 3-colorable. We show the first o(n ²) algorithm for 3-coloring vertices of triangle-free planar graphs. The time complexity of the algorithm is $\mathcal{O}(n\log n)Although deciding whether the vertices of a planar graph can be colored with three colors is NP-hard, the widely known Gr?tzsch’s theorem states that every triangle-free planar graph is 3-colorable. We show the first o(n ²) algorithm for 3-coloring vertices of triangle-free planar graphs. The time complexity of the algorithm is O(nlogn)\mathcal{O}(n\log n) .     

Subgraphs of 4-Regular Planar Graphs

We shall present an algorithm for determining whether or not a given planar graph H can ever be a subgraph of a 4-regular planar graph. The algorithm has running time O(|H|^2.5) and can be used to find an explicit 4-regular planar graph G⊃H if such a graph exists. It shall not matter whether we specify that H and G must be simple graphs or allow them to be multigraphs.     

基于遗传算法的平面图平面正交直线画图算法

提出了一种基于遗传算法的新的平面图平面正交直线画图算法,算法将平面图画图问题转化为约束优化问题,根据画图问题选定的美观准则构造约束函数,用遗传算法求解目标函数的最优解的近似值,从而得到平面图的平面正交直线画法。新算法的优点是方法简单,易于实现,画出的图形美观,算法稳定性好。实验结果表明,画图算法的最终结果不依赖于图的初始状态。