Two characterisations of the minimal triangulations of permutation graphs

A minimal triangulation of a graph is a chordal supergraph with an inclusion-minimal edge set. Minimal triangulations are obtained from adding edges only to minimal separators, completing minimal separators into cliques. Permutation graphs are the comparability graphs whose complements are also comparability graphs. Permutation graphs can be characterised as the intersection graphs of specially arranged line segments in the plane, which is called a permutation diagram. The minimal triangulations of permutation graphs are known to be interval graphs, and they can be obtained from permutation diagrams by applying a geometric operation, that corresponds to the completion of separators into cliques. We precisely specify this geometric completion process to obtain minimal triangulations, and we completely characterise those interval graphs that are minimal triangulations of permutation graphs.     

Dynamically maintaining split graphs

We present an algorithm that supports operations for modifying a split graph by adding edges or vertices and deleting edges, such that after each modification the graph is repaired to become a split graph in a minimal way. In particular, if the graph is not split after the modification, the algorithm computes a minimal, or if desired even a minimum, split completion or deletion of the modified graph. The motivation for such operations is similar to the motivation for fully dynamic algorithms for particular graph classes. In our case we allow all modifications to the graph and repair, rather than allowing only the modifications that keep the graph split. Fully dynamic algorithms of the latter kind are known for split graphs [L. Ibarra, Fully dynamic algorithms for chordal graphs and split graphs, Technical Report DCS-262-IR, University of Victoria, Canada, 2000].Our results can be used to design linear time algorithms for some recognition and completion problems, where the input is supplied in an on-line fashion.     

A vertex incremental approach for maintaining chordality

For a chordal graph G=(V,E), we study the problem of whether a new vertex u∉V and a given set of edges between u and vertices in V can be added to G so that the resulting graph remains chordal. We show how to resolve this efficiently, and at the same time, if the answer is no, specify a maximal subset of the proposed edges that can be added along with u, or conversely, a minimal set of extra edges that can be added in addition to the given set, so that the resulting graph is chordal. In order to do this, we give a new characterization of chordal graphs and, for each potential new edge uv, a characterization of the set of edges incident to u that also must be added to G along with uv. We propose a data structure that can compute and add each such set in O(n) time. Based on these results, we present an algorithm that computes both a minimal triangulation and a maximal chordal subgraph of an arbitrary input graph in O(nm) time, using a totally new vertex incremental approach. In contrast to previous algorithms, our process is on-line in that each new vertex is added without reconsidering any choice made at previous steps, and without requiring any knowledge of the vertices that might be added subsequently.     

Lex M versus MCS-M

We study the problem of minimal triangulation of graphs. One of the first algorithms to solve this problem was Lex M, which was presented in 1976. A new algorithm, and a simplification of Lex M called MCS-M, was presented in 2002. In this paper we compare these two algorithms and show that they produce the same set of triangulations, answering an open question mentioned by the authors of MCS-M.     

Minimal split completions

We study the problem of adding an inclusion minimal set of edges to a given arbitrary graph so that the resulting graph is a split graph, called a minimal split completion of the input graph. Minimal completions of arbitrary graphs into chordal and interval graphs have been studied previously, and new results have been added recently. We extend these previous results to split graphs by giving a linear-time algorithm for computing minimal split completions. We also give two characterizations of minimal split completions, which lead to a linear time algorithm for extracting a minimal split completion from any given split completion.We prove new properties of split graph that are both useful for our algorithms and interesting on their own. First, we present a new way of partitioning the vertices of a split graph uniquely into three subsets. Second, we prove that split graphs have the following property: given two split graphs on the same vertex set where one is a subgraph of the other, there is a sequence of edges that can be removed from the larger to obtain the smaller such that after each edge removal the modified graph is split.     

On a property of minimal triangulations

A graph H has the property MT, if for all graphs G, G is H-free if and only if every minimal (chordal) triangulation of G is H-free. We show that a graph H satisfies property MT if and only if H is edgeless, H is connected and is an induced subgraph of P₅, or H has two connected components and is an induced subgraph of 2P₃.This completes the results of Parra and Scheffler, who have shown that MT holds for H=P_k, the path on k vertices, if and only if k?5 [A. Parra, P. Scheffler, Characterizations and algorithmic applications of chordal graph embeddings, Discrete Applied Mathematics 79 (1997) 171-188], and of Meister, who proved that MT holds for ?P₂, ? copies of a P₂, if and only if ??2 [D. Meister, A complete characterisation of minimal triangulations of 2K₂-free graphs, Discrete Mathematics 306 (2006) 3327-3333].     

Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees

In this paper, we present algorithms for enumerating, without repetitions, all triangulations and non-crossing geometric spanning trees on a given set of n points in the plane under edge inclusion constraint (i.e., some edges are required to be included in the graph). We will first extend the lexicographically ordered triangulations introduced by Bespamyatnikh to the edge-constrained case, and then we prove that a set of all edge-constrained non-crossing spanning trees is connected via remove-add flips, based on the edge-constrained lexicographically largest triangulation. More specifically, we prove that all edge-constrained triangulations can be transformed to the lexicographically largest triangulation among them by O(n²) greedy flips, i.e., by greedily increasing the lexicographical ordering of the edge list, and a similar result also holds for a set of edge-constrained non-crossing spanning trees. Our enumeration algorithms generate each output triangulation and non-crossing spanning tree in O(loglogn) and O(n²) time, respectively, based on the reverse search technique.     

A linear time algorithm to list the minimal separators of chordal graphs

Kumar and Madhavan [Minimal vertex separators of chordal graphs, Discrete Appl. Math. 89 (1998) 155-168] gave a linear time algorithm to list all the minimal separators of a chordal graph. In this paper we give another linear time algorithm for the same purpose. While the algorithm of Kumar and Madhavan requires that a specific type of PEO, namely the MCS PEO is computed first, our algorithm works with any PEO. This is interesting when we consider the fact that there are other popular methods such as Lex BFS to compute a PEO for a given chordal graph.     

A generalization of chordal graphs

In a 3-connected planar triangulation, every circuit of length ≥ 4 divides the rest of the edges into two nontrivial parts (inside and outside) which are “separated” by the circuit. Neil Robertson asked to what extent triangulations are characterized by this property, and conjectured an answer. In this paper we prove his conjecture, that if G is simple and 3-connected and every circuit of length ≥ 4 has at least two “bridges,” then G may be built up by “clique-sums” starting from complete graphs and planar triangulations. This is a generalization of Dirac's theorem about chordal graphs.     

Minimal comparability completions of arbitrary graphs

A transitive orientation of an undirected graph is an assignment of directions to its edges so that these directed edges represent a transitive relation between the vertices of the graph. Not every graph has a transitive orientation, but every graph can be turned into a graph that has a transitive orientation, by adding edges. We study the problem of adding an inclusion minimal set of edges to an arbitrary graph so that the resulting graph is transitively orientable. We show that this problem can be solved in polynomial time, and we give a surprisingly simple algorithm for it. We use a vertex incremental approach in this algorithm, and we also give a more general result that describes graph classes Π for which Π completion of arbitrary graphs can be achieved through such a vertex incremental approach.     

On the Structure of Contractible Vertex Pairs in Chordal Graphs

An edge/non-edge in a k-connected graph is contractible if its contraction does not result in a graph of lower connectivity. We focus our study on contractible edges and non-edges in chordal graphs. Firstly, we characterize contractible edges in chordal graphs using properties of tree decompositions with respect to minimal vertex separators. Secondly, we show that in every chordal graph each non-edge is contractible. We also characterize non-edges whose contraction leaves a k-connected chordal graph.     

Generating the triangulations of the projective plane

Using the operations of face splitting and its dual, vertex splitting, one can generate all of the triangulations of the projective plane from two minimal triangulations. One of the minimal triangulations is the familiar embedding of the complete graph on 6 vertices. The other is a triangulation with 7 vertices.     

Triangulations intersect nicely

We show that there is a matching between the edges of any two triangulations of a planar point set such that an edge of one triangulation is matched either to the identical edge in the other triangulation or to an edge that crosses it. This theorem also holds for the triangles of the triangulations and in general independence systems. As an application, we give some lower bounds for the minimum-weight triangulation which can be computed in polynomial time by matching and network-flow techniques. We exhibit an easy-to-recognize class of point sets for which the minimum-weight triangulation coincides with the greedy triangulation.     

All roads lead to Rome—New search methods for the optimal triangulation problem

To perform efficient inference in Bayesian networks by means of a Junction Tree method, the network graph needs to be triangulated. The quality of this triangulation largely determines the efficiency of the subsequent inference, but the triangulation problem is unfortunately NP-hard. It is common for existing methods to use the treewidth criterion for optimality of a triangulation. However, this criterion may lead to a somewhat harder inference problem than the total table size criterion. We therefore investigate new methods for depth-first search and best-first search for finding optimal total table size triangulations. The search methods are made faster by efficient dynamic maintenance of the cliques of a graph. This problem was investigated by Stix, and in this paper we derive a new simple method based on the Bron-Kerbosch algorithm that compares favourably to Stix’ approach. The new approach is generic in the sense that it can be used with other algorithms than just Bron-Kerbosch. The algorithms for finding optimal triangulations are mainly supposed to be off-line methods, but they may form the basis for efficient any-time heuristics. Furthermore, the methods make it possible to evaluate the quality of heuristics precisely and allow us to discover parts of the search space that are most important to direct randomized sampling to.     

Lattice triangulations of $\mathbb{E}^3 $ and of the 3-torus

This paper gives answers to a few questions concerning tilings of Euclidean spaces where the tiles are topological simplices with curvilinear edges. We investigate lattice triangulations of Euclidean 3-space in the sense that the vertices form a lattice of rank 3 and such that the triangulation is invariant under all translations of that lattice. This is the dual concept of a primitive lattice tiling where the tiles are not assumed to be Euclidean polyhedra but only topological polyhedra. In 3-space there is a unique standard lattice triangulation by Euclidean tetrahedra (and with straight edges) but there are infinitely many non-standard lattice triangulations where the tetrahedra necessarily have certain curvilinear edges. From the view-point of Discrete Differential Geometry this tells us that there are such triangulations of 3-space which do not carry any flat discrete metric which is equivariant under the lattice. Furthermore, we investigate lattice triangulations of the 3-dimensional torus as quotients by a sublattice. The standard triangulation admits such quotients with any number n ≥ 15 of vertices. The unique one with 15 vertices is neighborly, i.e., any two vertices are joined by an edge. It turns out that for any odd n ≥ 17 there is an n-vertex neighborly triangulation of the 3-torus as a quotient of a certain non-standard lattice triangulation. Combinatorially, one can obtain these neighborly 3-tori as slight modifications of the boundary complexes of the cyclic 4-polytopes. As a kind of combinatorial surgery, this is an interesting construction by itself.     

Generating even triangulations on the torus

A triangulation on a surface $\mathbf{F}$ is a fixed embedding of a loopless graph on $\mathbf{F}$ with each face bounded by a cycle of length three. A triangulation is even if each vertex has even degree. We define two reductions for even triangulations on surfaces, called the 4-contraction and the twin-contraction. In this paper, we first determine the complete list of minimal 3-connected even triangulations on the torus with respect to these two reductions. Secondly, allowing a vertex of degree 2 and replacing the twin-contraction with another reduction, called the 2-contraction, we establish the list for all minimal even triangulations on the torus. We also describe several applications of the lists for solving problems on even triangulations.     

Unfolding of Surfaces

This paper deals with the approximation of the unfolding of a smooth globally developable surface (i.e. "isometric" to a domain of ) with a triangulation. We prove the following result: let T_n be a sequence of globally developable triangulations which tends to a globally developable smooth surface S in the Hausdorff sense. If the normals of T_n tend to the normals of S, then the shape of the unfolding of T_n tends to the shape of the unfolding of S. We also provide several examples: first, we show globally developable triangulations whose vertices are close to globally developable smooth surfaces; we also build sequences of globally developable triangulations inscribed on a sphere, with a number of vertices and edges tending to infinity. Finally, we also give an example of a triangulation with strictly negative Gauss curvature at any interior point, inscribed in a smooth surface with a strictly positive Gauss curvature. The Gauss curvature of these triangulations becomes positive (at each interior vertex) only by switching some of their edges.     

Characterizing and computing minimal cograph completions

A cograph completion of an arbitrary graph G is a cograph supergraph of G on the same vertex set. Such a completion is called minimal if the set of edges added to G is inclusion minimal. In this paper we present two results on minimal cograph completions. The first is a characterization that allows us to check in linear time whether a given cograph completion is minimal. The second result is a vertex incremental algorithm to compute a minimal cograph completion H of an arbitrary input graph G in O(|V(H)|+|E(H)|) time. An extended abstract of the result has been already presented at FAW 2008 [D. Lokshtanov, F. Mancini, C. Papadopoulos, Characterizing and computing minimal cograph completions, in: Proceedings of FAW’08-2nd International Frontiers of Algorithmics Workshop, in: LNCS, vol. 5059, 2008, pp. 147158. [1]].     

Generating weakly triangulated graphs

We show that a graph is weakly triangulated, or weakly chordal, if and only if it can be generated by starting with a graph with no edges, and repeatedly adding an edge, so that the new edge is not the middle edge of any chordless path with four vertices. This is a corollary of results due to Sritharan and Spinrad, and Hayward, Hoång and Maffray, and a natural analog of a theorem due to Fulkerson and Gross, which states that a graph is triangulated, or chordal, if and only if it can be generated by starting with a graph with no vertices, and repeatedly adding a vertex, so that the new vertex is not the middle vertex of any chordless path with three vertices. Our result answers the question of whether there exists a composition scheme that generates exactly the class of weakly triangulated graphs. © 1996 John Wiley & Sons, Inc.     

Generating realistic terrains with higher-order Delaunay triangulations

For hydrologic applications, terrain models should have few local minima, and drainage lines should coincide with edges. We show that triangulating a set of points with elevations such that the number of local minima of the resulting terrain is minimized is NP-hard for degenerate point sets. The same result applies when there are no degeneracies for higher-order Delaunay triangulations. Two heuristics are presented to reduce the number of local minima for higher-order Delaunay triangulations, which start out with the Delaunay triangulation. We give efficient algorithms for their implementation, and test on real-world data how well they perform. We also study another desirable drainage characteristic, few valley components, and how to obtain it for higher-order Delaunay triangulations. This gives rise to a third heuristic. Tables and visualizations show how the heuristics perform for the drainage characteristics on real-world data.