On embedding an outer-planar graph in a point set

Given an n-vertex outer-planar graph G and a set P of n points in the plane, we present an O(nlog³n) time and O(n) space algorithm to compute a straight-line embedding of G in P, improving upon the algorithm in [8,12] that requires O(n²) time. Our algorithm is near-optimal as there is an Ω(nlogn) lower bound for the problem [4]. We present a simpler O(nd) time and O(n) space algorithm to compute a straight-line embedding of G in P where lognd2n is the length of the longest vertex disjoint path in the dual of G. Therefore, the time complexity of the simpler algorithm varies between O(nlogn) and O(n²) depending on the value of d. More efficient algorithms are presented for certain restricted cases. If the dual of G is a path, then an optimal Θ(nlogn) time algorithm is presented. If the given point set is in convex position then we show that O(n) time suffices.     

A weak immersion relation on graphs and its applications

Weak immersion is a generalization of the immersion relation defined by Nash-Williams. A graph H is said to be weakly immersed in a graph G if H can be obtained from G by a sequence of these three operations: taking a subgraph, splitting a vertex, and lifting a pair of adjacent edges. The weak immersion relation has the useful property that finite graphs are well-quasi-ordered by it, which also holds for graphs with some vertices designated as terminals. As a result, any family of finite graphs that is closed under weak immersion can be characterized by a finite number of minimal forbidden graphs called obstructions. Weak immersion offers two advantages over immersion for practical applications. First, although closure under weak immersion implies closure under immersion, families can have significantly fewer obstructions under weak immersion. Hence weak immersion can provide simpler characterizations for closed families. Examples include graphs of bounded cutwidth and graphs of bounded multiway cutsize. The difference in the number of obstructions is at least exponential in the cutwidth and in the square-root of the multiway cutsize. Second, for every fixed graph H, there is a polynomial-time algorithm to decide whether H is weakly immersed in an input graph G. Consequently, there is a polynomial-time membership test for any family that is closed under weak immersion. In principle, testing for weak immersion is as fast as testing for immersion. Thus the simpler characterization provided by weak immersion may lead to faster membership algorithms.     

Algorithmic aspects of clique-transversal and clique-independent sets

A minimum clique-transversal set MCT(G) of a graph G=(V,E) is a set SV of minimum cardinality that meets all maximal cliques in G. A maximum clique-independent set MCI(G) of G is a set of maximum number of pairwise vertex-disjoint maximal cliques. We prove that the problem of finding an MCT(G) and an MCI(G) is NP-hard for cocomparability, planar, line and total graphs. As an interesting corollary we obtain that the problem of finding a minimum number of elements of a poset to meet all maximal antichains of the poset remains NP-hard even if the poset has height two, thereby generalizing a result of Duffas et al. (J. Combin. Theory Ser. A 58 (1991) 158–164). We present a polynomial algorithm for the above problems on Helly circular-arc graphs which is the first such algorithm for a class of graphs that is not clique-perfect. We also present polynomial algorithms for the weighted version of the clique-transversal problem on strongly chordal graphs, chordal graphs of bounded clique size, and cographs. The algorithms presented run in linear time for strongly chordal graphs and cographs. These mark the first attempts at the weighted version of the problem.     

Approximation of an open polygonal curve with a minimum number of circular arcs and biarcs

We present an algorithm for approximating a given open polygonal curve with a minimum number of circular arcs. In computer-aided manufacturing environments, the paths of cutting tools are usually described with circular arcs and straight line segments. Greedy algorithms for approximating a polygonal curve with curves of higher order can be found in the literature. Without theoretical bounds it is difficult to say anything about the quality of these algorithms. We present an algorithm which finds a series of circular arcs that approximate the polygonal curve while remaining within a given tolerance region. This series contains the minimum number of arcs of any such series. Our algorithm takes O(n²logn) time for an original polygonal chain with n vertices. Using a similar approach, we design an algorithm with a runtime of O(n²logn), for computing a tangent-continuous approximation with the minimum number of biarcs, for a sequence of points with given tangent directions.     

On a straight-line embedding problem of graphs

Let G be a planar graph with n vertices, v be a specified vertex of G, and P be a set of n points in the Euclidian plane in general position. A straight-line embedding of G onto P is an embedding of G onto whose images of vertices are distinct points in P and whose images of edges are (straight) line segments. In this paper, we classify into five classes those pairs of G and v such that for any P and any p P, G has a straight-line embedding onto P which maps v to p. We then show that all graphs in three of the classes indeed have such an embedding. This result gives a solution to a generalized version of the rooted-tree embedding problem raised by M. Perles.     

Normal Sylow subgroups and monomial Brauer characters

Let G be a finite group, p be a prime divisor of |G|, and P be a Sylow p-subgroup of G. We prove that P is normal in a solvable group G if |G : ker φ|p' = φ(1)p' for every nonlinear irreducible monomial p-Brauer character φ of G, where ker φ is the kernel of φ and φ(1)p' is the p'-part of φ(1).     

Strong equality of domination parameters in trees

We study the concept of strong equality of domination parameters. Let P₁ and P₂ be properties of vertex subsets of a graph, and assume that every subset of V(G) with property P₂ also has property P₁. Let ψ₁(G) and ψ₂(G), respectively, denote the minimum cardinalities of sets with properties P₁ and P₂, respectively. Then ψ₁(G)ψ₂(G). If ψ₁(G)=ψ₂(G) and every ψ₁(G)-set is also a ψ₂(G)-set, then we say ψ₁(G) strongly equals ψ₂(G), written ψ₁(G)≡ψ₂(G). We provide a constructive characterization of the trees T such that γ(T)≡i(T), where γ(T) and i(T) are the domination and independent domination numbers, respectively. A constructive characterization of the trees T for which γ(T)=γ_t(T), where γ_t(T) denotes the total domination number of T, is also presented.     

Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces

We present an optimal Θ(n)-time algorithm for the selection of a subset of the vertices of an n-vertex plane graph G so that each of the faces of G is covered by (i.e., incident with) one or more of the selected vertices. At most n/2 vertices are selected, matching the worst-case requirement. Analogous results for edge-covers are developed for two different notions of “coverage”. In particular, our linear-time algorithm selects at most n−2 edges to strongly cover G, at most n/3 diagonals to cover G, and in the case where G has no quadrilateral faces, at most n/3 edges to cover G. All these bounds are optimal in the worst-case. Most of our results flow from the study of a relaxation of the familiar notion of a 2-coloring of a plane graph which we call a face-respecting 2-coloring that permits monochromatic edges as long as there are no monochromatic faces. Our algorithms apply directly to the location of guards, utilities or illumination sources on the vertices or edges of polyhedral terrains, polyhedral surfaces, or planar subdivisions.     

Computing simple paths among obstacles

Given a set X of points in the plane, two distinguished points s,tX, and a set Φ of obstacles represented by line segments, we wish to compute a simple polygonal path from s to t that uses only points in X as vertices and avoids the obstacles in Φ. We present two results: (1) we show that finding such simple paths among arbitrary obstacles is NP-complete, and (2) we give a polynomial-time algorithm that computes simple paths when the obstacles form a simple polygon P and X is inside P. Our algorithm runs in time O(m²n²), where m is the number of vertices of P and n is the number of points in X.     

Topological entropy of a graph map

Let G be a graph and f : G → G be a continuous map. Denote by h(f), P(f), AP(f), R(f)and ω(x, f) the topological entropy of f, the set of periodic points of f, the set of almost periodic points of f, the set of recurrent points of f and the ω-limit set of x under f, respectively. In this paper,we show that the following statements are equivalent:(1) h(f) 0.(2) There exists an x ∈ G such that ω(x, f) ∩ P(f) = ? and ω(x, f) is an infinite set.(3) There exists an x ∈ G such that ω(x, f)contains two minimal sets.(4) There exist x, y ∈ G such that ω(x, f)-ω(y, f) is an uncountable set and ω(y, f) ∩ω(x, f) = ?.(5) There exist an x ∈ G and a closed subset A ? ω(x, f) with f(A) ? A such that ω(x, f)-A is an uncountable set.(6) R(f)-AP(f) = ?.(7) f |P(f)is not pointwise equicontinuous.     

Length-bounded disjoint paths in planar graphs

The following problem is considered: given: an undirected planar graph G=(V,E) embedded in , distinct pairs of vertices {r₁,s₁},…,{r_k,s_k} of G adjacent to the unbounded face, positive integers b₁,…,b_k and a function ; find: pairwise vertex-disjoint paths P₁,…,P_k such that for each i=1,…,k, P_i is a r_i−s_i-path and the sum of the l-length of all edges in P_i is at most b_i. It is shown that the problem is NP-hard in the strong sense. A pseudo-polynomial-time algorithm is given for the case of k=2.     

Multicolor routing in the undirected hypercube

An undirected routing problem is a pair (G,R) where G is an undirected graph and R is an undirected multigraph such that V(G)=V(R). A solution to an undirected routing problem (G,R) is a collection P of undirected paths of G (possibly containing multiple occurrences of the same path) such that edges of R are in one-to-one correspondence with the paths of P, with the path corresponding to edge {u,v} connecting u and v. We say that a collection of paths P is k-colorable if each path of P can be colored by one of the k colors so that the paths of the same color are edge-disjoint (each edge of G appears at most once in the paths of each single color). In the circuit-switched routing context, and in optical network applications in particular, it is desirable to find a solution to a routing problem that is colorable with as few colors as possible. Let Q_n denote the n-dimensional hypercube, for arbitrary n1. We show that a routing problem (Q_n,R) always admits a 4d-colorable solution where d is the maximum vertex degree of R. This improves over the 16d/2-color result which is implicit in the previous work of Aumann and Rabani [SODA95, pp. 567–576]. Since, for any positive d, there is a multigraph R of degree d such that any solution to (Q_n,R) requires at least d colors, our result is tight up to a factor of four. In fact, when d=1, it is tight up to a factor of two, since there is a graph of degree one (the antipodal matching) that requires two colors.     

路的字典积的邻和可区别边染色

图G的正常[k]-边染色σ是指颜色集合为[k]={1,2,…,k}的G的一个正常边染色.用w_σ（x）表示顶点x关联边的颜色之和,即w_σ（x）=∑_e∋x σ（e）,并称w_σ（x）关于σ的权.图G的k-邻和可区别边染色是指相邻顶点具有不同权的正常[k]-边染色,最小的k值称为G的邻和可区别边色数,记为χ'_∑（G）.现得到了路P_n与简单连通图H的字典积P_n[H]的邻和可区别边色数的精确值,其中H分别为正则第一类图、路、完全图的补图.     

Fast and reliable reconstruction of phylogenetic trees with indistinguishable edges

Phylogenetic reconstruction methods attempt to reconstruct a tree describing the evolution of a given set of species using sequences of characters (e.g. DNA) extracted from these species as input. A central goal in this area is to design algorithms which guarantee reliable reconstruction of the tree from short input sequences, assuming common stochastic models of evolution. The fast converging reconstruction algorithms introduced in the last decade dramatically reduced the sequence length required to guarantee accurate reconstruction of the entire tree. However, if the tree in question contains even few edges which cannot be reliably reconstructed from the input sequences, then known fast converging algorithms may fail to reliably reconstruct all or most of the other edges. This calls for an adaptive approach suggested in this paper, called adaptive fast convergence, in which the set of edges which can be reliably reconstructed gradually increases with the amount of information (length of input sequences) available to the algorithm. This paper presents an adaptive fast converging algorithm which returns a partially resolved topology containing no false edges: edges that cannot be reliably reconstructed are contracted into high degree vertices. We also present an upper bound on the weights of those contracted edges, which is determined by the length of input sequences and the depth of the tree. As such, the reconstruction guarantee provided by our algorithm for individual edges is significantly stronger than any previously published edge reconstruction guarantee. This fact, together with the optimal complexity of our algorithm (linear space and quadratic‐time), makes it appealing for practical use. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 350–384, 2011     

On the minimal reducible bound for outerplanar and planar graphs

Let L be the set of all additive and hereditary properties of graphs. For P₁, P₂ L we define the reducible property R = P₁ P₂ as follows: G P₁P₂ if there is a bipartition (V₁, V₂) of V(G) such that V₁ P₁ and V₂ P₂. For a property P L, a reducible property R is called a minimal reducible bound for P if P R and for each reducible property R′, R′ R → P R′. It is proved that the class of all outerplanar graphs has exactly two minimal reducible bounds in L. Some related problems for planar graphs are discussed.     

The power crust, unions of balls, and the medial axis transform

The medial axis transform (or MAT) is a representation of an object as an infinite union of balls. We consider approximating the MAT of a three-dimensional object, and its complement, with a finite union of balls. Using this approximate MAT we define a new piecewise-linear approximation to the object surface, which we call the power crust.

We assume that we are given as input a sufficiently dense sample of points from the object surface. We select a subset of the Voronoi balls of the sample, the polar balls, as the union of balls representation. We bound the geometric error of the union, and of the corresponding power crust, and show that both representations are topologically correct as well. Thus, our results provide a new algorithm for surface reconstruction from sample points. By construction, the power crust is always the boundary of a polyhedral solid, so we avoid the polygonization, hole-filling or manifold extraction steps used in previous algorithms.

The union of balls representation and the power crust have corresponding piecewise-linear dual representations, which in some sense approximate the medial axis. We show a geometric relationship between these duals and the medial axis by proving that, as the sampling density goes to infinity, the set of poles, the centers of the polar balls, converges to the medial axis.     

On Some Families of Smooth Affine Spherical Varieties of Full Rank

Let G be a complex connected reductive group. Losev has shown that a smooth affine spherical G-variety X is uniquely determined by its weight monoid, which is the set of irreducible representations of G that occur in the coordinate ring of X. In this paper we use a combinatorial characterization of the weight monoids of smooth affine spherical varieties to classify:(a) all such varieties for G = SL(2) × C~×and(b) all such varieties for G simple which have a G-saturated weight monoid of full rank. We also use the characterization and Knop's classification theorem for multiplicity free Hamiltonian manifolds to give a new proof of Woodward's result that every reflective Delzant polytope is the moment polytope of such a manifold.     

A note on transitive orientations with maximum sets of sources and sinks

Given a transitive orientation of a comparability graph G, a vertex of G is a source (sink) if it has indegree (outdegree) zero in , respectively. A source set of G is a subset of vertices formed by sources of some transitive orientation . A pair of subsets S,TV(G) is a source–sink pair of G when the vertices of S and T are sources and sinks, of some transitive orientation , respectively. We describe algorithms for finding a transitive orientation with a maximum source–sink pair in a comparability graph. The algorithms are applications of modular decomposition and are all of linear-time complexity.     

A note on minimum degree conditions for supereulerian graphs

A graph is called supereulerian if it has a spanning closed trail. Let G be a 2-edge-connected graph of order n such that each minimal edge cut SE(G) with |S|3 satisfies the property that each component of G−S has order at least (n−2)/5. We prove that either G is supereulerian or G belongs to one of two classes of exceptional graphs. Our results slightly improve earlier results of Catlin and Li. Furthermore, our main result implies the following strengthening of a theorem of Lai within the class of graphs with minimum degree δ4: If G is a 2-edge-connected graph of order n with δ(G)4 such that for every edge xyE(G) , we have max{d(x),d(y)}(n−2)/5−1, then either G is supereulerian or G belongs to one of two classes of exceptional graphs. We show that the condition δ(G)4 cannot be relaxed.