Search

Abstract Let P be a path graph of n vertices embedded in a metric space. We consider the problem of adding a new edge to P such that the diameter of the resulting graph is minimized. Previously (in ICALP 2015) the problem was solved in O (n log 3 ⁡ n) time. In this paper, based on new observations and different algorithmic techniques, we present an O (n log ⁡ n) time algorithm. [ABSTRACT FROM AUTHOR]

Let P = B ∪ R be a set of 2 n points in general position in the plane, where B is a set of n blue points and R a set of n red points. A BR-matching is a plane geometric perfect matching on P such that each edge has one red endpoint and one blue endpoint. Two BR -matchings are compatible if their union is also plane. The transformation graph of BR-matchings contains one node for each BR -matching and an edge joining two such nodes if and only if the corresponding two BR -matchings are compatible. At SoCG 2013 it has been shown by Aloupis, Barba, Langerman, and Souvaine that this transformation graph is always connected, but its diameter remained an open question. In this paper we provide an alternative proof for the connectivity of the transformation graph and prove an upper bound of 2 n for its diameter, which is asymptotically tight. Moreover, we present an O ( n 2 log ⁡ n ) time algorithm for constructing a transformation of length O ( n ) between two given BR -matchings. [ABSTRACT FROM AUTHOR]

Let P be a set of n points in general position in the plane which is partitioned into color classes. The set P is said to be color-balanced if the number of points of each color is at most [n/2] . Given a color-balanced point set P, a balanced cut is a line which partitions P into two color-balanced point sets, each of size at most 2n/3+1 . A colored matching of P is a perfect matching in which every edge connects two points of distinct colors by a straight line segment. A plane colored matching is a colored matching which is non-crossing. In this paper, we present an algorithm which computes a balanced cut for P in linear time. Consequently, we present an algorithm which computes a plane colored matching of P optimally in Θ(nlog n) time. [ABSTRACT FROM AUTHOR]

We consider the problem of embedding an undirected graph into hyperbolic space with minimum distortion. A fundamental problem in its own right, it has also drawn a great deal of interest from applied communities interested in empirical analysis of large-scale graphs. In this paper, we establish a connection between distortion and quasi-cyclicity of graphs, and use it to derive lower and upper bounds on metric distortion. Two particularly simple and natural graphs with large quasi-cyclicity are n -node cycles and n × n square lattices, and our lower bound shows that any hyperbolic-space embedding of these graphs incurs a multiplicative distortion of at least Ω ( n / log ⁡ n ) . This is in sharp contrast to Euclidean space, where both of these graphs can be embedded with only constant multiplicative distortion. We also establish a relation between quasi-cyclicity and δ -hyperbolicity of a graph as a way to prove upper bounds on the distortion. Using this relation, we show that graphs with small quasi-cyclicity can be embedded into hyperbolic space with only constant additive distortion. Finally, we also present an efficient (linear-time) randomized algorithm for embedding a graph with small quasi-cyclicity into hyperbolic space, so that with high probability at least a ( 1 − ε ) fraction of the node-pairs has only constant additive distortion. Our results also give a plausible theoretical explanation for why social networks have been observed to embed well into hyperbolic space: they tend to have small quasi-cyclicity. [ABSTRACT FROM AUTHOR]

Abstract: The distance preserving graph embedding problem is to embed the vertices of a given weighted graph onto points in d-dimensional Euclidean space for a constant d such that for each edge the distance between their corresponding endpoints is as close to the weight of the edge as possible. If the given graph is complete, that is, if the weights are given as a full matrix, then multi-dimensional scaling [Trevor Cox, Michael Cox, Multidimensional Scaling, second ed., Chapman & Hall CRC, 2001] can minimize the sum of squared embedding errors in quadratic time. A serious disadvantage of this approach is its quadratic space requirement. In this paper we develop a linear-space algorithm for this problem for the case when the weight of any edge can be computed in constant time. A key idea is to partition a set of n objects into disjoint subsets (clusters) of size such that the minimum inter cluster distance is maximized among all possible such partitions. Experimental results are included comparing the performance of the newly developed approach to the performance of the well-established least-squares multi-dimensional scaling approach [Trevor Cox, Michael Cox, Multidimensional Scaling, second ed., Chapman & Hall CRC, 2001] using three different applications. Although least-squares multi-dimensional scaling gave slightly more accurate results than our newly developed approach, least-squares multi-dimensional scaling ran out of memory for data sets larger than 15 000 vertices. [Copyright &y& Elsevier]

Abstract: This paper studies the problem of computing orthogonal drawings of graphs with labels on vertices and edges. Our research is mainly motivated by Software Engineering and Information Systems domains, where tools like UML diagrams and ER-diagrams are considered fundamental for the design of sophisticated systems and/or complex data bases collecting enormous amount of information. A label is modeled as a rectangle of prescribed width and height and it can be associated with either a vertex or an edge. Our drawing algorithms guarantee no overlaps between labels, vertices, and edges and take advantage of the information about the set of labels to compute the geometry of the drawing. Several additional optimization goals are taken into account. Namely, the labeled drawing can be required to have either minimum total edge length, or minimum width, or minimum height, or minimum area among those preserving a given orthogonal representation. All these goals lead to NP-hard problems. We present MILP models to compute optimal drawings with respect to the first three goals and an exact algorithm that is based on these models to compute a labeled drawing of minimum area. We also present several heuristics for computing compact labeled orthogonal drawings and experimentally validate their performances, comparing their solutions against the optimum. [Copyright &y& Elsevier]

Abstract: This paper investigates the basic problem of computing crossing-free straight-line 3D grid drawings of graphs such that the overall volume is small. Motivated by their relevance in the literature, we focus on families of graphs having constant queue number and on k-trees. We present algorithms that compute drawings of these families of graphs on 3D grids consisting of a constant number of parallel lines and such that the overall volume is linear. Lower bounds on the number of such grid lines are also provided. Our results extend and improve similar ones already described in the literature. [Copyright &y& Elsevier]

Abstract: In a visibility representation (VR for short) of a plane graph G, each vertex of G is represented by a horizontal line segment such that the line segments representing any two adjacent vertices of G are joined by a vertical line segment. Rosenstiehl and Tarjan [Discrete Comput. Geom. 1 (1986) 343–353] and Tamassia and Tollis [Discrete Comput. Geom. 1 (1986) 321–341] independently gave linear time VR algorithms for 2-connected plane graph. Using this approach, the height of the VR is bounded by , the width is bounded by . After that, some work has been done to find a more compact VR. Kant and He [Theoret. Comput. Sci. 172 (1997) 175–193] proved that a 4-connected plane graph has a VR with width bounded by . Kant [Internat. J. Comput. Geom. Appl. 7 (1997) 197–210] reduced the width bound to for general plane graphs. Recently, using a sophisticated greedy algorithm, Lin et al. reduced the width bound to [Proc. STACS''03, Lecture Notes in Computer Science, vol. 2607, Springer, Berlin, 2003, pp. 14–25]. In this paper, we prove that any plane graph G has a VR with width at most , which can be constructed by using the simple standard VR algorithm in [P. Rosenstiehl, R.E. Tarjan, Discrete Comput. Geom. 1 (1986) 343–353; R. Tamassia, I.G. Tollis, Discrete Comput. Geom. 1 (1986) 321–341]. [Copyright &y& Elsevier]