Computing upward topological book embeddings of upward planar digraphs

We describe a unified approach for studying book, point-set, and simultaneous embeddability problems of upward planar digraphs. The approach is based on a linear time strategy to compute an upward planar drawing of an upward planar digraph such that all vertices are collinear. Besides having impact in relevant application domains of graph drawing and computational geometry, the presented results open new research directions in the area of upward planarity with constraints of the positions of the vertices.     

Identifying aspirin polymorphs from combined DFT-based crystal structure prediction and solid-state NMR

A combined experimental and computational approach was used to distinguish between different polymorphs of the pharmaceutical drug aspirin. This method involves the use of ab initio random structure searching (AIRSS), a density functional theory (DFT)-based crystal structure prediction method for the high-accuracy prediction of polymorphic structures, with DFT calculations of nuclear magnetic resonance (NMR) parameters and solid-state NMR experiments at natural abundance. AIRSS was used to predict the crystal structures of form-I and form-II of aspirin. The root-mean-square deviation between experimental and calculated ¹H chemical shifts was used to identify form-I as the polymorph present in the experimental sample, the selection being successful despite the large similarities between the molecular environments in the crystals of the two polymorphs.     

A note on Hadwiger’s conjecture for W5-free graphs with independence number two

The Hadwiger number of a graph $G$, denoted $h\left(G\right)$, is the largest integer $t$ such that $G$ contains $K_t$ as a minor. A famous conjecture due to Hadwiger in 1943 states that for every graph $G$, $h\left(G\right)\ge \chi \left(G\right)$, where $\chi \left(G\right)$ denotes the chromatic number of $G$. Let $\alpha \left(G\right)$ denote the independence number of $G$. A graph is $H$-free if it does not contain the graph $H$ as an induced subgraph. In 2003, Plummer, Stiebitz and Toft proved that $h\left(G\right)\ge \chi \left(G\right)$ for all $H$-free graphs $G$ with $\alpha \left(G\right)\le 2$, where $H$ is any graph on four vertices with $\alpha \left(H\right)\le 2$, $H=C_5$, or $H$ is a particular graph on seven vertices. In 2010, Kriesell subsequently generalized the statement to include all forbidden subgraphs $H$ on five vertices with $\alpha \left(H\right)\le 2$. In this note, we prove that $h\left(G\right)\ge \chi \left(G\right)$ for all $W_5$-free graphs $G$ with $\alpha \left(G\right)\le 2$, where $W_5$ denotes the wheel on six vertices.     

3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects

We present a new data structure for a set of n convex simply-shaped fat objects in the plane, and use it to obtain efficient and rather simple solutions to several problems including (i) vertical ray shooting—preprocess a set of n non-intersecting convex simply-shaped flat objects in 3-space, whose xy-projections are fat, for efficient vertical ray shooting queries, (ii) point enclosure—preprocess a set C of n convex simply-shaped fat objects in the plane, so that the k objects containing a query point p can be reported efficiently, (iii) bounded-size range searching— preprocess a set C of n convex fat polygons, so that the k objects intersecting a “not-too-large” query polygon can be reported efficiently, and (iv) bounded-size segment shooting—preprocess a set C as in (iii), so that the first object (if exists) hit by a “not-too-long” oriented query segment can be found efficiently. For the first three problems we construct data structures of size O(λ_s(n)log³n), where s is the maximum number of intersections between the boundaries of the (xy-projections) of any pair of objects, and λ_s(n) is the maximum length of (n, s) Davenport-Schinzel sequences. The data structure for the fourth problem is of size O(λ_s(n)log²n). The query time in the first problem is O(log⁴n), the query time in the second and third problems is O(log³n + klog²n), and the query time in the fourth problem is O(log³n).

We also present a simple algorithm for computing a depth order for a set as in (i), that is based on the solution to the vertical ray shooting problem. (A depth order for , if exists, is a linear order of , such that, if K₁, K₂ and K₁ lies vertically above K₂, then K₁ precedes K₂.) Unlike the algorithm of Agarwal et al. (1995) that might output a false order when a depth order does not exist, the new algorithm is able to determine whether such an order exists, and it is often more efficient in practical situations than the former algorithm.     

Pseudo-Strong Regularity Around a Set

A generalization of strong regularity around a vertex subset C of a graph Γ, which makes sense even if Γis non-regular, is studied. Such a structure appears, together with a kind of distance-regularity around C , when an spectral bound concerning the so-called predistance polynomial of C is attained. As a main consequence of these results, it is shown that a regular (connected) graph Γwith d + 1 distinct eigenvalues is distance-regular, and its distance- d graph Γ d is strongly regular with parameters a = c , if and only if the number of vertices at distance d from each vertex satisfies an expression which depends only on the order of Γand the different eigenvalues of Γ.     

Drawing c-planar biconnected clustered graphs

In a graph, a cluster is a set of vertices, and two clusters are said to be non-intersecting if they are disjoint or one of them is contained in the other. A clustered graph C consists of a graph G and a set of non-intersecting clusters. In this paper, we assume that C has a compound planar drawing and each cluster induces a biconnected subgraph. Then we show that such a clustered graph admits a drawing in the plane such that (i) edges are drawn as straight-line segments with no edge crossing and (ii) the boundary of the biconnected subgraph induced by each cluster is a convex polygon.