24 citations · 37 across the 21 of their papers we have counts for
22 papers
Lunar Generalizations of the Euclidean Minimum Spanning Tree in the Plane and their Expected Costs
Ondřej Draganov, Herbert Edelsbrunner, Sophie Rosenmeier +1
Motivated by the recent introduction of chromatic persistent homology, we generalize the Euclidean minimum spanning tree (EMST) for points in to the lunar EMST f…
How Close is a Tree to a Euclidean Minimum Spanning Tree?
Todor Antić, Jiří Fiala, Jelena Glišić +8
Let be a straight-line crossing-free drawing of a tree . A \emph{bad pair} in is a pair of non-adjacent vertices of whose Euclidean distance in is smaller than t…
How many times can two minimum spanning trees cross?
Todor Antić, Morteza Saghafian, Maria Saumell +3
Let be a generic set of points in the plane, and let be a coloring of in two colors. We are interested in the number of crossings between the minimum spanni…
Edge-Constrained Hamiltonian Paths on a Point Set
Todor Antić, Aleksa Džuklevski, Jiří Fiala +5
Let S be a set of distinct points in general position in the Euclidean plane. A plane Hamiltonian path on S is a crossing-free geometric path such that every point of S is a vertex…
Expected Length of the Euclidean Minimum Spanning Tree and 1-norms of Chromatic Persistence Diagrams in the Plane
Ondřej Draganov, Herbert Edelsbrunner, Sophie Rosenmeier +1
Let be the constant such that the expected length of the Euclidean minimum spanning tree of random points in the unit square is in the limit, when goes to…
Covering Complete Geometric Graphs by Monotone Paths
Adrian Dumitrescu, János Pach, Morteza Saghafian +1
Given a set of points (vertices) in general position in the plane, the \emph{complete geometric graph} consists of all segments (edges) between the…
On Spheres with Points Inside
Herbert Edelsbrunner, Alexey Garber, Morteza Saghafian
We generalize the classic definition of Delaunay triangulation and prove that for a locally finite and coarsely dense generic point set, , the -simplic…
On the MST-ratio: Theoretical Bounds and Complexity of Finding the Maximum
Afrouz Jabal Ameli, Faezeh Motiei, Morteza Saghafian
Given a finite set of red and blue points in $\Rspace^d$, the MST-ratio is defined as the total length of the Euclidean minimum spanning trees of the red points and the blue points…
Chromatic Topological Data Analysis
Sebastiano Cultrera di Montesano, Ondrej Draganov, Herbert Edelsbrunner +1
Exploring the shape of point configurations has been a key driver in the evolution of TDA (short for topological data analysis) since its infancy. This survey illustrates the recen…
The Euclidean MST-ratio for Bi-colored Lattices
Sebastiano Cultrera di Montesano, Ondřej Draganov, Herbert Edelsbrunner +1
Given a finite set, , and a subset, , the \emph{MST-ratio} is the combined length of the minimum spanning trees of and …
Order-2 Delaunay Triangulations Optimize Angles
Herbert Edelsbrunner, Alexey Garber, Morteza Saghafian
The local angle property of the (order-) Delaunay triangulations of a generic set in asserts that the sum of two angles opposite a common edge is less than . T…
Decomposition of Geometric Graphs into Star Forests
János Pach, Morteza Saghafian, Patrick Schnider
We solve a problem of Dujmović and Wood (2007) by showing that a complete convex geometric graph on vertices cannot be decomposed into fewer than star-forests, each consi…
On the Size of Chromatic Delaunay Mosaics
Ranita Biswas, Sebastiano Cultrera di Montesano, Ondřej Draganov +2
Given a locally finite set and a coloring , we introduce the chromatic Delaunay mosaic of , which is a Delaunay mosaic…
Flips in Two-dimensional Hypertriangulations
Herbert Edelsbrunner, Alexey Garber, Mohadese Ghafari +2
We study flips in hypertriangulations of planar points sets. Here a level- hypertriangulation of points in the planes is a subdivision induced by the projection of a -hyp…
Chromatic Alpha Complexes
Sebastiano Cultrera di Montesano, Ondřej Draganov, Herbert Edelsbrunner +1
Motivated by applications in the medical sciences, we study finite chromatic sets in Euclidean space from a topological perspective. Based on the persistent homology for images, ke…
On Angles in Higher Order Brillouin Tessellations and Related Tilings in the Plane
Herbert Edelsbrunner, Alexey Garber, Mohadese Ghafari +2
For a locally finite set in , the order- Brillouin tessellations form an infinite sequence of convex face-to-face tilings of the plane. If the set is coarsely dens…
Brillouin Zones of Integer Lattices and Their Perturbations
Herbert Edelsbrunner, Alexey Garber, Mohadese Ghafari +3
For a locally finite set, , the -th Brillouin zone of is the region of points for which is the -th smallest…
Chromatic Number and Dichromatic Polynomial of Digraphs
Saeed Akbari, Amir Hossein Ghodrati, Afrouz Jabalameli +1
Let be a graph of order . It is well-known that , where is the independence number of and is the degree se…
On -tuple and -tuple total domination numbers of regular graphs
Sharareh Alipour, Amir Jafari, Morteza Saghafian
Let be a connected graph of order , whose minimum vertex degree is at least . A subset of vertices in is a -tuple total dominating set if every vertex of i…
Is there any polynomial upper bound for the universal labeling of graphs?
Arash Ahadi, Ali Dehghan, Morteza Saghafian
A {\it universal labeling} of a graph is a labeling of the edge set in such that in every orientation of for every two adjacent vertices and , the sum of…
Improving the Bounds On Murty_Simon Conjecture
Afrouz Jabalameli, Amin behjati, Morteza Saghafian +3
A graph is said to be diameter--critical if its diameter is and removal of any of its edges increases its diameter. A beautiful conjecture by Murty and Simon, says that ever…
On a Bounded Budget Network Creation Game
Shayan Ehsani, Saber Shokat Fadaee, MohammadAmin Fazli +4
We consider a network creation game in which each player (vertex) has a fixed budget to establish links to other players. In our model, each link has unit price and each agent trie…