Plane Embeddings of Planar Graph Metrics

Embedding metrics into constant-dimensional geometric spaces, such as the Euclidean plane, is relatively poorly understood. Motivated by applications in visualization, ad-hoc networks, and molecular reconstruction, we consider the natural problem of embedding shortest-path metrics of unweighted planar graphs (planar graph metrics) into the Euclidean plane. It is known that, in the special case of shortest-path metrics of trees, embedding into the plane requires distortion in the worst case [M1], [BMMV], and surprisingly, this worst-case upper bound provides the best known approximation algorithm for minimizing distortion. We answer an open question posed in this work and highlighted by Matousek [M3] by proving that some planar graph metrics require distortion in any embedding into the plane, proving the first separation between these two types of graph metrics. We also prove that some planar graph metrics require distortion in any crossing-free straight-line embedding into the plane, suggesting a separation between low-distortion plane embedding and the well-studied notion of crossing-free straight-line planar drawings. Finally, on the upper-bound side, we prove that all outerplanar graph metrics can be embedded into the plane with distortion, generalizing the previous results on trees (both the worst-case bound and the approximation algorithm) and building techniques for handling cycles in plane embeddings of graph metrics.     

Some asymptotically optimal one-sided embeddings of trees of similar formulas into rectangular lattices

We consider the problem of optimally placing trees of formulas in rectangular lattices. We construct and study two types of these trees and corresponding ways of placing (embedding) them into such lattices. The first is based on perfect binary trees, while the second is based on special binary trees. For the second type of tree embeddings, we prove asymptotic optimality among the trees of all formulas similar to the initial formula of no greater depth.     

Metric Embeddings—Beyond One-Dimensional Distortion

The extensive study of metric spaces and their embeddings has so far focused on embeddings that preserve pairwise distances. A very intriguing concept introduced by Feige allows us to quantify the extent to which larger structures are preserved by a given embedding. We investigate this concept, focusing on several major graph families such as paths, trees, cubes, and expanders. We find some similarities to the regular (pairwise) distortion, as well as some striking differences.     

On Average Distortion of Embedding Metrics into the Line

We introduce and study the notion of the average distortion of a nonexpanding embedding of one metric space into another. Less sensitive than the multiplicative metric distortion, the average distortion captures well the global picture and, overall, is a quite interesting new measure of metric proximity, related to the concentration of measure phenomenon. The paper mostly deals with embeddings into the real line with a low (as much as it is possible) average distortion. Our main technical contribution is that the shortest-path metrics of special (e.g., planar, bounded treewidth, etc.) undirected weighted graphs can be embedded into the line with constant average distortion. This has implications, e.g., on the value of the MinCut–MaxFlow gap in uniform-demand multicommodity flows on such graphs. A preliminary version of this paper has appeared at STOC’03, pp. 156–162. Supported in part by a grant ISF-247-02-10.5.     

Discrete quasi-Einstein metrics and combinatorial curvature flows in 3-dimension

Motivated by the definition of combinatorial scalar curvature given by Cooper and Rivin, we introduce a new combinatorial scalar curvature. Then we define the discrete quasi-Einstein metric, which is a combinatorial analogue of the constant scalar curvature metric in smooth case. We find that discrete quasi-Einstein metric is critical point of both the combinatorial Yamabe functional and the quadratic energy functional we defined on triangulated 3-manifolds. We introduce combinatorial curvature flows, including a new type of combinatorial Yamabe flow, to study the discrete quasi-Einstein metrics and prove that the flows produce solutions converging to discrete quasi-Einstein metrics if the initial normalized quadratic energy is small enough. As a corollary, we prove that nonsingular solution of the combinatorial Yamabe flow with nonpositive initial curvatures converges to discrete quasi-Einstein metric. The proof relies on a careful analysis of the discrete dual-Laplacian, which we interpret as the Jacobian matrix of curvature map.     

Amenability,locally finite spaces,and bi-lipschitz embeddings

We define the isoperimetric constant for any locally finite metric space and we study the property of having isoperimetric constant equal to zero. This property, called Small Neighborhood property, clearly extends amenability to any locally finite space. Therefore, we start making a comparison between this property and other notions of amenability for locally finite metric spaces that have been proposed by Gromov, Lafontaine and Pansu, by Ceccherini-Silberstein, Grigorchuk and de la Harpe and by Block and Weinberger. We discuss possible applications of the property SN in the study of embedding a metric space into another one. In particular, we propose three results: we prove that a certain class of metric graphs that are isometrically embeddable into Hilbert spaces must have the property SN. We also show, by a simple example, that this result is not true replacing property SN with amenability. As a second result, we prove that many spaces with uniform bounded geometry having a bi-lipschitz embedding into Euclidean spaces must have the property SN. Finally, we prove a Bourgain-like theorem for metric trees: a metric tree with uniform bounded geometry and without property SN does not have bi-lipschitz embeddings into finite-dimensional Hilbert spaces.     

On dominatedl 1 metrics

We introduce and study a classl ₁ ^dom (ρ) ofl ₁-embeddable metrics corresponding to a given metric ρ. This class is defined as the set of all convex combinations of ρ-dominated line metrics. Such metrics were implicitly used before in several constuctions of low-distortion embeddings intol _p -spaces, such as Bourgain’s embedding of an arbitrary metric ρ onn points withO(logh) distortion. Our main result is that the gap between the distortions of embedding of a finite metric ρ of sizen intol ₂ versus intol ₁ ^dom (ρ) is at most , and that this bound is essentially tight. A significant part of the paper is devoted to proving lower bounds on distortion of such embeddings. We also discuss some general properties and concrete examples. Research by J. M. supported by Charles University grants No. 158/99 and 159/99. Part of the work by Y. R. was done during his visit at the Charles University in Prague partially supported by these grants, by the grant GAČR 201/99/0242, and by Haifa University grant for Promotion of Research.     

Embedding the Kepler Problem as a Surface of Revolution

Solutions of the planar Kepler problem with fixed energy h determine geodesics of the corresponding Jacobi–Maupertuis metric. This is a Riemannian metric on ?² if h ? 0 or on a disk D ? ?² if h < 0. The metric is singular at the origin (the collision singularity) and also on the boundary of the disk when h < 0. The Kepler problem and the corresponding metric are invariant under rotations of the plane and it is natural to wonder whether the metric can be realized as a surface of revolution in ?³ or some other simple space. In this note, we use elementary methods to study the geometry of the Kepler metric and the embedding problem. Embeddings of the metrics with h ? 0 as surfaces of revolution in ?³ are constructed explicitly but no such embedding exists for h < 0 due to a problem near the boundary of the disk. We prove a theorem showing that the same problem occurs for every analytic central force potential. Returning to the Kepler metric, we rule out embeddings in the three-sphere or hyperbolic space, but succeed in constructing an embedding in four-dimensional Minkowski spacetime. Indeed, there are many such embeddings.     

Quasi-isometries between visual hyperbolic spaces

We prove that a power quasi-symmetric (or PQ-symmetric) homeomorphism between two complete metric spaces can be extended to a quasi-isometry between their hyperbolic approximations. This result can be used to prove that two visual Gromov hyperbolic spaces are quasi-isometric if and only if there is a PQ-symmetric homeomorphism between their boundaries with bounded visual metrics. Also, in the case of trees, we prove that two geodesically complete trees are quasi-isometric if and only if there is a PQ-symmetric homeomorphism between their boundaries with visual metrics based at infinity. We also give a characterization for a map to be PQ-symmetric based on the relative distortion of subsets.     

On the existence of solutions of the system of Peterson-codazzi and gauss equations

This paper is concerned with isometric embeddings of complete two-dimensional metrics, defined on the plane, whose curvature is bounded by negative constants (metrics of type L). It is proved that under certain conditions any horocycle in a metric of type L (an analog of a horocycle in the Lobachevskii plane) admits a C³-isometric embedding into E³. The proof is based on the construction of a smooth solution of the system of Peterson-Codazzi and Gauss equations in an infinite domain.     

Advances in metric embedding theory

Metric Embedding plays an important role in a vast range of application areas such as computer vision, computational biology, machine learning, networking, statistics, and mathematical psychology, to name a few. The mathematical theory of metric embedding is well studied in both pure and applied analysis and has more recently been a source of interest for computer scientists as well. Most of this work is focused on the development of bi-Lipschitz mappings between metric spaces. In this paper we present new concepts in metric embeddings as well as new embedding methods for metric spaces. We focus on finite metric spaces, however some of the concepts and methods are applicable in other settings as well.One of the main cornerstones in finite metric embedding theory is a celebrated theorem of Bourgain which states that every finite metric space on n points embeds in Euclidean space with distortion. Bourgain?s result is best possible when considering the worst case distortion over all pairs of points in the metric space. Yet, it is natural to ask: can an embedding do much better in terms of the average distortion? Indeed, in most practical applications of metric embedding the main criteria for the quality of an embedding is its average distortion over all pairs.In this paper we provide an embedding with constant average distortion for arbitrary metric spaces, while maintaining the same worst case bound provided by Bourgain?s theorem. In fact, our embedding possesses a much stronger property. We define the ?q-distortion of a uniformly distributed pair of points. Our embedding achieves the best possible ?q-distortion for all 1?q?∞simultaneously.The results are based on novel embedding methods which improve on previous methods in another important aspect: the dimension of the host space. The dimension of an embedding is of very high importance in particular in applications and much effort has been invested in analyzing it. However, no previous result improved the bound on the dimension which can be derived from Bourgain?s embedding. Our embedding methods achieve better dimension, and in fact, shed new light on another fundamental question in metric embedding, which is: whether the embedding dimension of a metric space is related to its intrinsic dimension? I.e., whether the dimension in which it can be embedded in some real normed space is related to the intrinsic dimension which is reflected by the inherent geometry of the space, measured by the space?s doubling dimension. The existence of such an embedding was conjectured by Assouad,⁴and was later posed as an open problem in several papers. Our embeddings give the first positive result of this type showing any finite metric space obtains a low distortion (and constant average distortion) embedding in Euclidean space in dimension proportional to its doubling dimension.Underlying our results is a novel embedding method. Probabilistic metric decomposition techniques have played a central role in the field of finite metric embedding in recent years. Here we introduce a novel notion of probabilistic metric decompositions which comes particularly natural in the context of embedding. Our new methodology provides a unified approach to all known results on embedding of arbitrary finite metric spaces. Moreover, as described above, with some additional ideas they allow to get far stronger results.The results presented in this paper⁵have been the basis for further developments both within the field of metric embedding and in other areas such as graph theory, distributed computing and algorithms. We present a comprehensive study of the notions and concepts introduced here and provide additional extensions, related results and some examples of algorithmic applications.     

Volume in General Metric Spaces

A central question in the geometry of finite metric spaces is how well can an arbitrary metric space be “faithfully preserved” by a mapping into Euclidean space. In this paper we present an algorithmic embedding which obtains a new strong measure of faithful preservation: not only does it (approximately) preserve distances between pairs of points, but also the volume of any set of \(k\) points. Such embeddings are known as volume preserving embeddings. We provide the first volume preserving embedding that obtains constant average volume distortion for sets of any fixed size. Moreover, our embedding provides constant bounds on all bounded moments of the volume distortion while maintaining the best possible worst-case volume distortion. Feige, in his seminal work on volume preserving embeddings defined the volume of a set \(S = \{v_1, \ldots , v_k \}\) of points in a general metric space: the product of the distances from \(v_i\) to \(\{ v_1, \dots , v_{i-1} \}\) , normalized by \(\tfrac{1}{(k-1)!}\) , where the ordering of the points is that given by Prim’s minimum spanning tree algorithm. Feige also related this notion to the maximal Euclidean volume that a Lipschitz embedding of \(S\) into Euclidean space can achieve. Syntactically this definition is similar to the computation of volume in Euclidean spaces, which however is invariant to the order in which the points are taken. We show that a similar robustness property holds for Feige’s definition: the use of any other order in the product affects volume \(^{1/(k-1)}\) by only a constant factor. Our robustness result is of independent interest as it presents a new competitive analysis for the greedy algorithm on a variant of the online Steiner tree problem where the cost of buying an edge is logarithmic in its length. This robustness property allows us to obtain our results on volume preserving embedding.     

Kähler-Einstein metrics and projective embeddings

We prove that the complex projective space equipped with its Fubini-Study metric admits no compact Kähler-Einstein submanifold with nonpositive Einstein constant. In particular, the Calabi-Yau metrics carried by an algebraic K3 surface cannot be realized by projective embeddings.     

Metrical characterization of super-reflexivity and linear type of Banach spaces

We prove that a Banach space X is not super-reflexive if and only if the hyperbolic infinite tree embeds metrically into X. We improve one implication of J.Bourgain’s result who gave a metrical characterization of super-reflexivity in Banach spaces in terms of uniform embeddings of the finite trees. A characterization of the linear type for Banach spaces is given using the embedding of the infinite tree equipped with the metrics d _p induced by the ℓ _p norms. Received: 2 August 2006, Revised: 10 April 2007     

Métriques autoduales sur la boule

A conformal metric on a 4-ball induces on the boundary 3-sphere a conformal metric and a trace-free second fundamental form. Conversely, such a data on the 3-sphere is the boundary of a unique selfdual conformal metric, defined in a neighborhood of the sphere. In this paper we characterize the conformal metrics and trace-free second fundamental forms on the 3-sphere (close to the standard round metric) which are boundaries of selfdual conformal metrics on the whole 4-ball. When the data on the boundary is reduced to a conformal metric (the trace-free part of the second fundamental form vanishes), one may hope to find in the conformal class of the filling metric an Einstein metric, with a pole of order 2 on the boundary. We determine which conformal metrics on the 3-sphere are boundaries of such selfdual Einstein metrics on the 4-ball. In particular, this implies the Positive Frequency Conjecture of LeBrun. The proof uses twistor theory, which enables to translate the problem in terms of complex analysis; this leads us to prove a criterion for certain integrable CR structures of signature (1,1) to be fillable by a complex domain. Finally, we solve an analogous, higher dimensional problem: selfdual Einstein metrics are replaced by quaternionic-K?hler metrics, and conformal structures on the boundary by quaternionic contact structures (previously introduced by the author); in contrast with the 4-dimensional case, we prove that any small deformation of the standard quaternionic contact structure on the (4m−1)-sphere is the boundary of a quaternionic-K?hler metric on the (4m)-ball. Oblatum 29-XI-2000 & 7-XI-2001?Published online: 1 February 2002     

Fundamental polytopes of metric trees via parallel connections of matroids

We tackle the problem of a combinatorial classification of finite metric spaces via their fundamental polytopes, as suggested by Vershik (2010).In this paper we consider a hyperplane arrangement associated to every split pseudometric and, for tree-like metrics, we study the combinatorics of its underlying matroid.

• •We give explicit formulas for the face numbers of fundamental polytopes and Lipschitz polytopes of all tree-like metrics.
• •We characterize the metric trees for which the fundamental polytope is simplicial.

     

On optimality conditions in optimization problems on solutions of operator equations

We study optimization problems in the presence of connection in the form of operator equations defined in Banach spaces. We prove necessary conditions for optimality of first and second order, for example generalizing the Pontryagin maximal principle for these problems. It is not our purpose to state the most general necessary optimality conditions or to compile a list of all necessary conditions that characterize optimal control in any particular minimization problem. In the present article we describe schemes for obtaining necessary conditions for optimality on solutions of general operator equations defined in Banach spaces, and the scheme discussed here does not require that there be no global functional constraints on the controlling parameters. As an example, in a particular Banach space we prove an optimality condition using the Pontryagin-McShane variation. Bibliography: 20 titles. Translated fromProblemy Matematicheskoi Fiziki, 1998, pp. 55–67.     

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.

Curvature bounds by isoperimetric comparison for normalized Ricci flow on the two-sphere

We prove a comparison theorem for the isoperimetric profiles of solutions of the normalized Ricci flow on the two-sphere: If the isoperimetric profile of the initial metric is greater than that of some positively curved axisymmetric metric, then the inequality remains true for the isoperimetric profiles of the evolved metrics. We apply this using the Rosenau solution as the model metric to deduce sharp time-dependent curvature bounds for arbitrary solutions of the normalized Ricci flow on the two-sphere. This gives a simple and direct proof of convergence to a constant curvature metric without use of any blowup or compactness arguments, Harnack estimates, or any classification of behaviour near singularities.     

Generalized k-ary tanglegrams on level graphs: A satisfiability-based approach and its evaluation

A tanglegram is a pair of (not necessarily binary) trees on the same set of leaves with matching leaves in the two trees joined by an edge. Tanglegrams are widely used in computational biology to compare evolutionary histories of species. In this work we present a formulation of two related combinatorial embedding problems concerning tanglegrams in terms of CNF-formulas. The first problem is known as the planar embedding and the second as the crossing minimization problem. We show that our satisfiability-based encoding of these problems can handle a much more general case with more than two, not necessarily binary or complete, trees defined on arbitrary sets of leaves and allowed to vary their layouts. Furthermore, we present an experimental comparison of our technique and several known heuristics for solving generalized binary tanglegrams, showing its competitive performance and efficiency and thus proving its practical usability.