Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs

We give two new linear-time algorithms, one for recognizing proper circular-arc graphs and the other for recognizing unit circular-arc graphs. Both algorithms provide either a model for the input graph, or a certificate that proves that such a model does not exist and can be authenticated in O(n) time. No other previous algorithm for each of these two graph classes provides a certificate for its result.     

Solving the path cover problem on circular-arc graphs by using an approximation algorithm

A path cover of a graph G=(V,E) is a family of vertex-disjoint paths that covers all vertices in V. Given a graph G, the path cover problem is to find a path cover of minimum cardinality. This paper presents a simple O(n)-time approximation algorithm for the path cover problem on circular-arc graphs given a set of n arcs with endpoints sorted. The cardinality of the path cover found by the approximation algorithm is at most one more than the optimal one. By using the result, we reduce the path cover problem on circular-arc graphs to the Hamiltonian cycle and Hamiltonian path problems on the same class of graphs in O(n) time. Hence the complexity of the path cover problem on circular-arc graphs is the same as those of the Hamiltonian cycle and Hamiltonian path problems on circular-arc graphs.     

Algorithms for clique-independent sets on subclasses of circular-arc graphs

A circular-arc graph is the intersection graph of arcs on a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. A clique-independent set of a graph is a set of pairwise disjoint cliques of the graph. It is NP-hard to compute the maximum cardinality of a clique-independent set for a general graph. In the present paper, we propose polynomial time algorithms for finding the maximum cardinality and weight of a clique-independent set of a -free CA graph. Also, we apply the algorithms to the special case of an HCA graph. The complexity of the proposed algorithm for the cardinality problem in HCA graphs is O(n). This represents an improvement over the existing algorithm by Guruswami and Pandu Rangan, whose complexity is O(n²). These algorithms suppose that an HCA model of the graph is given.     

Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs

A locally connected spanning tree of a graph G is a spanning tree T of G such that the set of all neighbors of v in T induces a connected subgraph of G for every v∈V(G). The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively.     

Equivalences and the complete hierarchy of intersection graphs of paths in a tree

An (h,s,t)-representation of a graph G consists of a collection of subtrees of a tree T, where each subtree corresponds to a vertex in G, such that (i) the maximum degree of T is at most h, (ii) every subtree has maximum degree at most s, (iii) there is an edge between two vertices in the graph G if and only if the corresponding subtrees have at least t vertices in common in T. The class of graphs that have an (h,s,t)-representation is denoted by [h,s,t]. It is well known that the class of chordal graphs corresponds to the class [3, 3, 1]. Moreover, it was proved by Jamison and Mulder that chordal graphs correspond to orthodox-[3, 3, 1] graphs defined below.In this paper, we investigate the class of [h,2,t] graphs, i.e., the intersection graphs of paths in a tree. The [h,2,1] graphs are also known as path graphs [F. Gavril, A recognition algorithm for the intersection graphs of paths in trees, Discrete Math. 23 (1978) 211-227] or VPT graphs [M.C. Golumbic, R.E. Jamison, Edge and vertex intersection of paths in a tree, Discrete Math. 55 (1985) 151-159], and [h,2,2] graphs are known as the EPT graphs. We consider variations of [h,2,t] by three main parameters: h, t and whether the graph has an orthodox representation. We give the complete hierarchy of relationships between the classes of weakly chordal, chordal, [h,2,t] and orthodox-[h,2,t] graphs for varied values of h and t.     

Lexicographic orientation and representation algorithms for comparability graphs,proper circular arc graphs,and proper interval graphs

We introduce a simple new technique which allows us to solve several problems that can be formulated as seeking a suitable orientation of a given undirected graph. In particular, we use this technique to recognize and transitively orient comparability graphs, to recognize and represent proper circular arc graphs, and to recognize and represent proper interval graphs. As a consequence, we derive and represent proper interval graphs. As a consequence, we derive simple new proofs of a theorem of Ghouila-Houri and a theorem of Skrien. Our algorithms are conceptually simpler than (and often of comparable efficiency to) the existing algorithms for these problems. © 1995 John Wiley & Sons, Inc.     

Testing set proportionality and the Ádám isomorphism of circulant graphs

Given two k element subsets , we give a quasi-linear algorithm to either find such that S=λT or prove that no such λ exists.This question is closely related to isomorphism testing of circulant graphs and has recently been studied in the literature.     

Two methods for the generation of chordal graphs

In this paper two methods for automatic generation of connected chordal graphs are proposed: the first one is based on new results concerning the dynamic maintenance of chordality under edge insertions; the second is based on expansion/merging of maximal cliques. Theoretical and experimental results are presented. In both methods, chordality is preserved along the whole generation process. L. Markenzon’s research is partially supported by grant 301068/2003-8, CNPq, Brazil.     

The Roberts characterization of proper and unit interval graphs

In this note, a constructive proof that the classes of proper interval graphs and unit interval graphs coincide is given, a result originally established by Fred S. Roberts. Additionally, the proof yields a linear-time and space algorithm to compute a unit interval representation, given a proper interval graph as input.     

Geometric separation and exact solutions for the parameterized independent set problem on disk graphs

We consider the parameterized problem, whether for a given set  of n disks (of bounded radius ratio) in the Euclidean plane there exists a set of k non-intersecting disks. For this problem, we expose an algorithm running in time that is—to our knowledge—the first algorithm with running time bounded by an exponential with a sublinear exponent. For λ-precision disk graphs of bounded radius ratio, we show that the problem is fixed parameter tractable with a running time  . The results are based on problem kernelization and a new “geometric ( -separator) theorem” which holds for all disk graphs of bounded radius ratio. The presented algorithm then performs, in a first step, a “geometric problem kernelization” and, in a second step, uses divide-and-conquer based on our new “geometric separator theorem.”     

On the computational complexity of partial covers of Theta graphs

By use of elementary geometric arguments we prove the existence of a special integral solution of a certain system of linear equations. The existence of such a solution then yields the NP-hardness of the decision problem on the existence of locally injective homomorphisms to Theta graphs with three distinct odd path lengths.     

Separator theorems and Turán-type results for planar intersection graphs

We establish several geometric extensions of the Lipton-Tarjan separator theorem for planar graphs. For instance, we show that any collection C of Jordan curves in the plane with a total of m crossings has a partition into three parts C=S∪C₁∪C₂ such that , , and no element of C₁ has a point in common with any element of C₂. These results are used to obtain various properties of intersection patterns of geometric objects in the plane. In particular, we prove that if a graph G can be obtained as the intersection graph of n convex sets in the plane and it contains no complete bipartite graph Kt,t as a subgraph, then the number of edges of G cannot exceed ctn, for a suitable constant ct.     

Computational complexity of reconstruction and isomorphism testing for designs and line graphs

Graphs with high symmetry or regularity are the main source for experimentally hard instances of the notoriously difficult graph isomorphism problem. In this paper, we study the computational complexity of isomorphism testing for line graphs of t-(v,k,λ) designs. For this class of highly regular graphs, we obtain a worst-case running time of O(vlogv+O(1)) for bounded parameters t, k, λ.In a first step, our approach makes use of the Babai-Luks algorithm to compute canonical forms of t-designs. In a second step, we show that t-designs can be reconstructed from their line graphs in polynomial-time. The first is algebraic in nature, the second purely combinatorial. For both, profound structural knowledge in design theory is required. Our results extend earlier complexity results about isomorphism testing of graphs generated from Steiner triple systems and block designs.     

Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction

A spanning tree T of a graph G is called a treet-spanner, if the distance between any two vertices in T is at most t-times their distance in G. A graph that has a tree t-spanner is called a treet-spanner admissible graph. The problem of deciding whether a graph is tree t-spanner admissible is NP-complete for any fixed t≥4, and is linearly solvable for t=1 and t=2. The case t=3 still remains open. A directed path graph is called a 2-sep directed path graph if all of its minimal a−b vertex separator for every pair of non-adjacent vertices a and b are of size two. Le and Le [H.-O. Le, V.B. Le, Optimal tree 3-spanners in directed path graphs, Networks 34 (2) (1999) 81-87] showed that directed path graphs admit tree 3-spanners. However, this result has been shown to be incorrect by Panda and Das [B.S. Panda, Anita Das, On tree 3-spanners in directed path graphs, Networks 50 (3) (2007) 203-210]. In fact, this paper observes that even the class of 2-sep directed path graphs, which is a proper subclass of directed path graphs, need not admit tree 3-spanners in general. It, then, presents a structural characterization of tree 3-spanner admissible 2-sep directed path graphs. Based on this characterization, a linear time recognition algorithm for tree 3-spanner admissible 2-sep directed path graphs is presented. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep directed path graph is proposed.