Drawing Planar Graphs Symmetrically, II: Biconnected Planar Graphs

Symmetry is one of the most important aesthetic criteria in graph drawing because it reveals the structure in the graph. This paper discusses symmetric drawings of biconnected planar graphs. More specifically, we discuss geometric automorphisms, that is, automorphisms of a graph G that can be represented as symmetries of a drawing of G. Finding geometric automorphisms is the first and most difficult step in constructing symmetric drawings of graphs. The problem of determining whether a given graph has a non-trivial geometric automorphism is NP-complete for general graphs. In this paper we present a linear time algorithm for finding planar geometric automorphisms of biconnected planar graphs. A drawing algorithm is also discussed.     

时序图中Top-k稠密子图查询算法研究

稠密子图的查询是图分析领域的重要研究问题之一,在社交用户相关性分析、Web中社群分析等方面都有着广泛的应用.目前,关于稠密子图查询的研究工作主要基于静态图.而在实际应用中,时序信息会对稠密子图查询产生重要的影响,使得图拓扑结构随时间序列不断发生变化,包含的信息量也不断增加,使得已有的针对静态图的查找方法不再适用于时序图...     

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.     

Clique Numbers of Random Subgraphs of Some Distance Graphs

We consider a class of graphs G(n, r, s) = (V (n, r),E(n, r, s)) defined as follows:

$$V(n,r) = \{ x = ({x_{1,}},{x_2}...{x_n}):{x_i} \in \{ 0,1\} ,{x_{1,}} + {x_2} + ... + {x_n} = r\} ,E(n,r,s) = \{ \{ x,y\} :(x,y) = s\} $$

where (x, y) is the Euclidean scalar product. We study random subgraphs G(G(n, r, s), p) with edges independently chosen from the set E(n, r, s) with probability p each. We find nontrivial lower and upper bounds on the clique number of such graphs.

     

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.     

Edge-Packing in Planar Graphs

Maximum G Edge-Packing (EPack _G ) is the problem of finding the maximum number of edge-disjoint isomorphic copies of a fixed guest graph G in a host graph H . This paper investigates the computational complexity of edge-packing for planar guests and planar hosts. Edge-packing is solvable in polynomial time when both G and H are trees. Edge-packing is solvable in linear time when H is outerplanar and G is either a 3-cycle or a k -star (a graph isomorphic to K _1,k ). Edge-packing is NP-complete when H is planar and G is either a cycle or a tree with edges. A strategy for developing polynomial-time approximation algorithms for planar hosts is exemplified by a linear-time approximation algorithm that finds a k -star edge-packing of size at least half the optimal. Received May 1995, and in revised form November 1995, and in final form December 1997.     

Disk Embeddings of Planar Graphs

Given a planar graph $G=(V,E)$ and a rooted forest ${\FF}=(V_{\FF}, A_{\FF})$ with leaf set $V$, we wish to decide whether $G$ has a plane embedding $\GG$ satisfying the following condition: There are $|V_{\FF}|-|V|$ pairwise noncrossing Jordan curves in the plane one-to-one corresponding to the nonleaf vertices of ${\FF}$ such that for every nonleaf vertex $f$ of ${\FF}$, the interior of the curve $\JJ_f$ corresponding to $f$ contains all the leaf descendants of $f$ in ${\FF}$ but contains no other leaves of ${\FF}$. This problem arises from theoretical studies in geographic database systems. It is unknown whether this problem can be solved in polynomial time. This paper presents an almost linear-time algorithm for a nontrivial special case where the set of leaf descendants of each nonleaf vertex $f$ in ${\FF}$ induces a connected subgraph of $G$.     

A New Approximation Algorithm for Finding Heavy Planar Subgraphs

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.     

Holant Problems for 3-Regular Graphs with Complex Edge Functions

We study several embeddings of doubling metrics into low dimensional normed spaces, in particular into ? ₂ and ? _∞ . Doubling metrics are a robust class of metric spaces that have low intrinsic dimension, and often occur in applications. Understanding the dimension required for a concise representation of such metrics is a fundamental open problem in the area of metric embedding. Here we show that the n-vertex Laakso graph can be embedded into constant dimensional ? ₂ with the best possible distortion, which has implications for possible approaches to the above problem.     

Many Distances in Planar Graphs

We show how to compute in O(n ^4/3log?^1/3 n+n ^2/3 k ^2/3log?n) time the distance between k given pairs of vertices of a planar graph G with n vertices. This improves previous results whenever (n/log?n)^5/6≤k≤n ²/log?⁶ n. As an application, we speed up previous algorithms for computing the dilation of geometric planar graphs.     

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.     

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) .     

Dynamically Switching Vertices in Planar Graphs

We consider graphs whose vertices may be in one of two different states: either on or off . We wish to maintain dynamically such graphs under an intermixed sequence of updates and queries. An update may reverse the status of a vertex, by switching it either on or off , and may insert a new edge or delete an existing edge. A query tests whether any two given vertices are connected in the subgraph induced by the vertices that are on . We give efficient algorithms that maintain information about connectivity on planar graphs in O( log ³ n) amortized time per query, insert, delete, switch-on, and switch-off operation over sequences of at least Ω(n) operations, where n is the number of vertices of the graph. Received September 1997; revised January 1999.     

Fast Minor Testing in Planar Graphs

Minor Containment is a fundamental problem in Algorithmic Graph Theory used as a subroutine in numerous graph algorithms. A model of a graph H in a graph G is a set of disjoint connected subgraphs of G indexed by the vertices of H, such that if {u,v} is an edge of H, then there is an edge of G between components C _u and C _v . A graph H is a minor of G if G contains a model of H as a subgraph. We give an algorithm that, given a planar n-vertex graph G and an h-vertex graph H, either finds in time $\mathcal{O}(2^{\mathcal{O}(h)} \cdot n +n^{2}\cdot\log n)$ a model of H in G, or correctly concludes that G does not contain H as a minor. Our algorithm is the first single-exponential algorithm for this problem and improves all previous minor testing algorithms in planar graphs. Our technique is based on a novel approach called partially embedded dynamic programming.     

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.     

Clique-Width for 4-Vertex Forbidden Subgraphs

Clique-width of graphs is a major new concept with respect to efficiency of graph algorithms. The notion of clique-width extends the one of treewidth, since bounded treewidth implies bounded clique-width. We give a complete classification of all graph classes defined by forbidden induced subgraphs of at most four vertices with respect to bounded or unbounded clique-width.     

New Linear-Time Algorithms for Edge-Coloring Planar Graphs

We show efficient algorithms for edge-coloring planar graphs. Our main result is a linear-time algorithm for coloring planar graphs with maximum degree Δ with max {Δ,9} colors. Thus the coloring is optimal for graphs with maximum degree Δ≥9. Moreover for Δ=4,5,6 we give linear-time algorithms that use Δ+2 colors. These results improve over the algorithms of Chrobak and Yung (J. Algorithms 10:35–51, 1989) and of Chrobak and Nishizeki (J. Algorithms 11:102–116, 1990) which color planar graphs using max {Δ,19} colors in linear time or using max {Δ,9} colors in time. R. Cole supported in part by NSF grants CCR0105678 and CCF0515127 and IDM0414763. Ł. Kowalik supported in part by KBN grant 4T11C04425. Part of this work was done while Ł. Kowalik was staying at the Max Planck Institute in Saarbruecken, Germany.     

Lower Bound on the Minimum Number of Edges in Subgraphs of Johnson Graphs

Problems of Information Transmission - We prove a new lower bound on the minimum number of edges in subgraphs of Johnson graphs in the general case.     

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.