Voronoi drawings of trees

We study the problem of characterizing sets of points whose Voronoi diagrams are trees and if so, what are the combinatorial properties of these trees. The second part of the problem can be naturally turned into the following graph drawing question: Given a tree T, can one represent T so that the resulting drawing is a Voronoi diagram of some set of points? We investigate the problem both in the Euclidean and in the Manhattan metric. The major contributions of this paper are as follows.

• We characterize those trees that can be drawn as Voronoi diagrams in the Euclidean metric.

• We characterize those sets of points whose Voronoi diagrams are trees in the Manhattan metric.

• We show that the maximum vertex degree of any tree that can be drawn as a Manhattan Voronoi diagram is at most five and prove that this bound is tight.

• We characterize those binary trees that can be drawn as Manhattan Voronoi diagrams.

Low distortion euclidean embeddings of trees

We consider the problem of embedding a certain finite metric space to the Euclidean space, trying to keep the bi-Lipschitz constant as small as possible. We introduce the notationc ₂(X, d) for the least distortion with which the metric space (X, d) may be embedded in a Euclidean space. It is known that if (X, d) is a metric space withn points, thenc ₂(X, d)≤0(logn) and the bound is tight. LetT be a tree withn vertices, andd be the metric induced by it. We show thatc ₂(T, d)≤0(log logn), that is we provide an embeddingf of its vertices to the Euclidean space, such thatd(x, y)≤‖f(x)−f(y) ‖≤c log lognd(x, y) for some constantc. Supported in part by grants from the Israeli Academy of Sciences and the US-Israel Binational Science Foundation. Supported in part by NSF under grants CCR-9215293 and by DIMACS, which is supported by NSF grant STC-91-19999 and by the New Jersey Commission on Science and Technology.     

Tight embeddings of partial quadrilateral packings

Let f(n;C₄) be the smallest integer such that, given any set of edge disjoint quadrilaterals on n vertices, one can extend it into a complete quadrilateral decomposition by including at most f(n;C₄) additional vertices. It is known, and it is easy to show, that . Here we settle the longstanding problem that .     

Counting labelled trees with given indegree sequence

For a labelled tree on the vertex set [n]:={1,2,…,n}, define the direction of each edge ij to be i→j if i<j. The indegree sequence of T can be considered as a partition λ?n−1. The enumeration of trees with a given indegree sequence arises in counting secant planes of curves in projective spaces. Recently Ethan Cotterill conjectured a formula for the number of trees on [n] with indegree sequence corresponding to a partition λ. In this paper we give two proofs of Cotterill's conjecture: one is “semi-combinatorial” based on induction, the other is a bijective proof.     

Pathwidth, trees, and random embeddings

We prove that, for every integer k≥1, every shortest-path metric on a graph of pathwidth k embeds into a distribution over random trees with distortion at most c=c(k), independent of the graph size. A well-known conjecture of Gupta, Newman, Rabinovich, and Sinclair [12] states that for every minor-closed family of graphs F, there is a constant c(F) such that the multi-commodity max-flow/min-cut gap for every flow instance on a graph from F is at most c(F). The preceding embedding theorem is used to prove this conjecture whenever the family F does not contain all trees.     

Laplacian coefficients of trees with a given bipartition

Let G be a graph of order n and the Laplacian characteristic polynomial of G. Zhou and Gutman [19] proved that among all trees of order n, the kth coefficient c_k is largest when the tree is a path and is smallest for a star. In this paper, for two given positive integers p and q(p≤q), we characterize the trees with a given bipartition (p,q) which have the minimal and second minimal Laplacian coefficients.     

Polynomial area bounds for MST embeddings of trees

In their seminal paper on geometric minimum spanning trees, Monma and Suri (1992) [31] showed how to embed any tree of maximum degree 5 as a minimum spanning tree in the Euclidean plane. The embeddings provided by their algorithm require area O(n²²)×O(n²²) and the authors conjectured that an improvement below cn×cn is not possible, for some constant c>0. In this paper, we show how to construct MST embeddings of arbitrary trees of maximum degree 3 and 4 within polynomial area.     

Ordered partitions and drawings of rooted plane trees

We study the bounded regions in a generic slice of the hyperplane arrangement in Rⁿ${\mathbb{R}}^n$ consisting of the hyperplanes defined by _xi$x_i$ and _xi+_xj$x_i+x_j$. The bounded regions are in bijection with several classes of combinatorial objects, including the ordered partitions of [n]$\left[n\right]$ all of whose left-to-right minima occur at odd locations and the drawings of rooted plane trees with n+1$n+1$ vertices. These are sequences of rooted plane trees such that each tree in a sequence can be obtained from the next one by removing a leaf.     

Extremal energies of trees with a given domination number

The energy of a graph is defined as the sum of the absolute values of the eigenvalues of its adjacency matrix. Let T(n,γ) be the set of trees of order n and with domination number γ. In this paper, we characterize the tree from T(n,γ) with the minimal energy, and determine the tree from T(n,γ) where n=kγ with maximal energy for .     

An inverse problem for Sturm‐Liouville operators on trees with partial information given on the potentials

We consider Sturm‐Liouville operators on geometrical graphs without cycles (trees) with singular potentials from the class . We suppose that the potentials are known on a part of the graph, and study the so‐called partial inverse problem, which consists in recovering the potentials on the remaining part of the graph from some parts of several spectra. The main results of the paper are the uniqueness theorem and a constructive procedure for the solution of the partial inverse problem. Our method is based on the completeness and the Riesz‐basis property of special systems of vector functions and the reduction of the partial inverse problem to the complete one on a part of the graph.     

2-restricted extensions of partial embeddings of graphs

Let K be a subgraph of G. Suppose that we have a 2-cell embedding of K in some surface and that for each K-bridge in G, one or two simple embeddings in faces of K are prescribed. Obstructions for existence of extensions of the embedding of K to an embedding of G are studied. It is shown that minimal obstructions possess certain combinatorial structure that can be described in an algebraic way by means of forcing chains of K-bridges. The geometric structure of minimal obstructions is also described. It is shown that they have “millipede” structure that was observed earlier in some special cases (disc, Möbius band). As a consequence it is proved that if one is allowed to reroute the branches of K, one can obtain a subgraph K′ of G homeomorphic to K for which an obstruction of bounded branch size exists. The precise combinatorial and geometric structure of corresponding obstructions can be used to get a linear time algorithm for either finding an embedding extension or discovering minimal obstructions.     

A bijective enumeration of labeled trees with given indegree sequence

For a labeled tree on the vertex set {1,2,…,n}, the local direction of each edge (ij) is from i to j if i<j. For a rooted tree, there is also a natural global direction of edges towards the root. The number of edges pointing to a vertex is called its indegree. Thus the local (resp. global) indegree sequence λ=e₁¹e₂²… of a tree on the vertex set {1,2,…,n} is a partition of n−1. We construct a bijection from (unrooted) trees to rooted trees such that the local indegree sequence of a (unrooted) tree equals the global indegree sequence of the corresponding rooted tree. Combining with a Prüfer-like code for rooted labeled trees, we obtain a bijective proof of a recent conjecture by Cotterill and also solve two open problems proposed by Du and Yin. We also prove a q-multisum binomial coefficient identity which confirms another conjecture of Cotterill in a very special case.     

Enumeration of coloured plane trees with a given type partition

Tutte's result for the number of planted plane trees with a given degree partition is rederived by a variety of methods and in particular by a simple piecewise construction technique. A theorem of Gordon and Temple is applied in order to give a general relationship between the number of planted plane trees and the number of rooted plane trees and the degree partition restriction is generalised to type partition. The piecewise construction method is successfully used to derive the number of planted plane trees with a given 2-colour degree partition, also derived by Tutte, and an algorithm for the k-coloured case is developed. This algorithm may be used to obtain more specific results. These models are relevant to the statistical mechanics of polymers and this is discussed briefly.