Elena Arseneva
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Elena Arseneva has a total of 44 co-authors. Here are the top co-authors by number of shared publications:
- Stefan Langerman
Computer Science Department Université Libre de Bruxelles Belgium
3 shared publications - Linda Kleist
Universität Potsdam
2 shared publications - Pilar Cano
Universite Libre de Bruxelles
2 shared publications Prosenjit Bose
Carleton University
2 shared publications- Ahmad Biniaz
School of Computer Science, University of Windsor, Windsor, Canada
1 shared publication - Aleksandar Markovic
TU Eindhoven, Eindhoven, The Netherlands
1 shared publication
Latest Publications
- Open Access
- 18 October 2023
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 71 (4) , 1429-1455
Adjacency Graphs of Polyhedral Surfaces
We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in $${\mathbb {R}}^3$$ . We show that every graph is realizable as a polyhedral surface with arbitrary polygonal cells, and that this is not true if we require the cells to be convex. In particular, if the given graph contains $$K_5$$ , $$K_{5,81}$$ , or any nonplanar 3-tree as a subgraph, no such realization exists. On the other hand, all planar graphs, $$K_{4,4}$$ , and $$K_{3,5}$$ can be realized with convex cells. The same holds for any subdivision of any graph where each edge is subdivided at least once, and, by a result from McMullen et al. (Isr. J. Math. 46(1–2), 127–144 (1983)), for any hypercube. Our results have implications on the maximum density of graphs describing polyhedral surfaces with convex cells: The realizability of hypercubes shows that the maximum number of edges over all realizable n-vertex graphs is in $$\Omega (n\log n)$$ . From the non-realizability of $$K_{5,81}$$ , we obtain that any realizable n-vertex graph has $${\mathcal {O}}(n^{9/5})$$ edges. As such, these graphs can be considerably denser than planar graphs, but not arbitrarily dense.- 18 October 2023
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 71 (4) , 1429-1455
Open AccessAdjacency Graphs of Polyhedral Surfaces
We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in $${\mathbb {R}}^3$$ . We show that every graph is realizable as a polyhedral surface with arbitrary polygonal cells, and that this is not true if we require the cells to be convex. In particular, if the given graph contains $$K_5$$ , $$K_{5,81}$$ , or any nonplanar 3-tree as a subgraph, no such realization exists. On the other hand, all planar graphs, $$K_{4,4}$$ , and $$K_{3,5}$$ can be realized with convex cells. The same holds for any subdivision of any graph where each edge is subdivided at least once, and, by a result from McMullen et al. (Isr. J. Math. 46(1–2), 127–144 (1983)), for any hypercube. Our results have implications on the maximum density of graphs describing polyhedral surfaces with convex cells: The realizability of hypercubes shows that the maximum number of edges over all realizable n-vertex graphs is in $$\Omega (n\log n)$$ . From the non-realizability of $$K_{5,81}$$ , we obtain that any realizable n-vertex graph has $${\mathcal {O}}(n^{9/5})$$ edges. As such, these graphs can be considerably denser than planar graphs, but not arbitrarily dense. - Open Access
Morphing tree drawings in a small 3D grid
We study crossing-free grid morphs for planar tree drawings using 3D. A morph consists of morphing steps, where vertices move simultaneously along straight-line trajectories at constant speeds. A crossing-free morph is known between two drawings of an $n$-vertex planar graph $G$ with $\mathcal{O}(n)$ morphing steps and using the third dimension it can be reduced to $\mathcal{O}(\log n)$ for an $n$-vertex tree [Arseneva et al.\ 2019]. However, these morphs do not bound one practical parameter, the resolution. Can the number of steps be reduced substantially by using the third dimension while keeping the resolution bounded throughout the morph? We answer this question in an affirmative and present a 3D non-crossing morph between two planar grid drawings of an $n$-vertex tree in $\mathcal{O}(\sqrt{n} \log n)$ morphing steps. Each intermediate drawing lies in a $3D$ grid of polynomial volume.Open AccessMorphing tree drawings in a small 3D grid
We study crossing-free grid morphs for planar tree drawings using 3D. A morph consists of morphing steps, where vertices move simultaneously along straight-line trajectories at constant speeds. A crossing-free morph is known between two drawings of an $n$-vertex planar graph $G$ with $\mathcal{O}(n)$ morphing steps and using the third dimension it can be reduced to $\mathcal{O}(\log n)$ for an $n$-vertex tree [Arseneva et al.\ 2019]. However, these morphs do not bound one practical parameter, the resolution. Can the number of steps be reduced substantially by using the third dimension while keeping the resolution bounded throughout the morph? We answer this question in an affirmative and present a 3D non-crossing morph between two planar grid drawings of an $n$-vertex tree in $\mathcal{O}(\sqrt{n} \log n)$ morphing steps. Each intermediate drawing lies in a $3D$ grid of polynomial volume. - 16 February 2021
- Published by Springer Nature
- p. 234-246
Upward Point Set Embeddings of Paths and Trees
- 16 February 2021
- Published by Springer Nature
- p. 234-246
Upward Point Set Embeddings of Paths and Trees
- 11 July 2020
- Published by Elsevier in Computational Geometry
- Vol. 92, 101685
Rectilinear link diameter and radius in a rectilinear polygonal domain
- 11 July 2020
- Published by Elsevier in Computational Geometry
- Vol. 92, 101685
Rectilinear link diameter and radius in a rectilinear polygonal domain
- Open Access
A Complete List of All Convex Polyhedra Made by Gluing Regular Pentagons
We give a complete description of all convex polyhedra whose surface can be constructed from several congruent regular pentagons by folding and gluing them edge to edge. Our method of determining the graph structure of the polyhedra from a gluing is of independent interest and can be used in other similar settings.
Open AccessA Complete List of All Convex Polyhedra Made by Gluing Regular Pentagons
We give a complete description of all convex polyhedra whose surface can be constructed from several congruent regular pentagons by folding and gluing them edge to edge. Our method of determining the graph structure of the polyhedra from a gluing is of independent interest and can be used in other similar settings.
- Open Access
Compatible Paths on Labelled Point Sets
Let $P$ and $Q$ be finite point sets of the same cardinality in $\mathbb{R}^2$, each labelled from $1$ to $n$. Two noncrossing geometric graphs $G_P$ and $G_Q$ spanning $P$ and $Q$, respectively, are called compatible if for every face $f$ in $G_P$, there exists a corresponding face in $G_Q$ with the same clockwise ordering of the vertices on its boundary as in $f$. In particular, $G_P$ and $G_Q$ must be straight-line embeddings of the same connected $n$-vertex graph. Deciding whether two labelled point sets admit compatible geometric paths is known to be NP-complete. We give polynomial-time algorithms to find compatible paths or report that none exist in three scenarios: $O(n)$ time for points in convex position; $O(n^2)$ time for two simple polygons, where the paths are restricted to remain inside the closed polygons; and $O(n^2 \log n)$ time for points in general position if the paths are restricted to be monotone.Open AccessCompatible Paths on Labelled Point Sets
Let $P$ and $Q$ be finite point sets of the same cardinality in $\mathbb{R}^2$, each labelled from $1$ to $n$. Two noncrossing geometric graphs $G_P$ and $G_Q$ spanning $P$ and $Q$, respectively, are called compatible if for every face $f$ in $G_P$, there exists a corresponding face in $G_Q$ with the same clockwise ordering of the vertices on its boundary as in $f$. In particular, $G_P$ and $G_Q$ must be straight-line embeddings of the same connected $n$-vertex graph. Deciding whether two labelled point sets admit compatible geometric paths is known to be NP-complete. We give polynomial-time algorithms to find compatible paths or report that none exist in three scenarios: $O(n)$ time for points in convex position; $O(n^2)$ time for two simple polygons, where the paths are restricted to remain inside the closed polygons; and $O(n^2 \log n)$ time for points in general position if the paths are restricted to be monotone. - Open Access
Which convex polyhedra can be made by gluing regular hexagons?
Which convex 3D polyhedra can be obtained by gluing several regular hexagons edge-to-edge? It turns out that there are only 15 possible types of shapes, 5 of which are doubly-covered 2D polygons. We give examples for most of them, including all simplicial and all flat shapes, and give a characterization for the latter ones. It is open whether the remaining can be realized.
Open AccessWhich convex polyhedra can be made by gluing regular hexagons?
Which convex 3D polyhedra can be obtained by gluing several regular hexagons edge-to-edge? It turns out that there are only 15 possible types of shapes, 5 of which are doubly-covered 2D polygons. We give examples for most of them, including all simplicial and all flat shapes, and give a characterization for the latter ones. It is open whether the remaining can be realized.
- 9 October 2019
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 36 (2) , 339-345
Which Convex Polyhedra Can Be Made by Gluing Regular Hexagons?
- 9 October 2019
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 36 (2) , 339-345
Which Convex Polyhedra Can Be Made by Gluing Regular Hexagons?
- 16 May 2019
- Published by Springer Nature
- p. 25-37
Reconstructing a Convex Polygon from Its $\omega $-cloud- 16 May 2019
- Published by Springer Nature
- p. 25-37
Reconstructing a Convex Polygon from Its $\omega $-cloud- Open Access
Reconstructing a convex polygon from its $ω$-cloud
An $\omega$-wedge is the closed set of points contained between two rays that are emanating from a single point (the apex), and are separated by an angle $\omega < \pi$. Given a convex polygon $P$, we place the $\omega$-wedge such that $P$ is inside the wedge and both rays are tangent to $P$. The set of apex positions of all such placements of the $\omega$-wedge is called the $\omega$-cloud of $P$. We investigate reconstructing a polygon $P$ from its $\omega$-cloud. Previous work on reconstructing $P$ from probes with the $\omega$-wedge required knowledge of the points of tangency between $P$ and the two rays of the $\omega$-wedge in addition to the location of the apex. Here we consider the setting where the maximal $\omega$-cloud alone is given. We give two conditions under which it uniquely defines $P$: (i) when $\omega < \pi$ is fixed/given, or (ii) when what is known is that $\omega < \pi/2$. We show that if neither of these two conditions hold, then $P$ may not be unique. We show that, when the uniqueness conditions hold, the polygon $P$ can be reconstructed in $O(n)$ time with $O(1)$ working space in addition to the input, where $n$ is the number of arcs in the input $\omega$-cloud.Open AccessReconstructing a convex polygon from its $ω$-cloud
An $\omega$-wedge is the closed set of points contained between two rays that are emanating from a single point (the apex), and are separated by an angle $\omega < \pi$. Given a convex polygon $P$, we place the $\omega$-wedge such that $P$ is inside the wedge and both rays are tangent to $P$. The set of apex positions of all such placements of the $\omega$-wedge is called the $\omega$-cloud of $P$. We investigate reconstructing a polygon $P$ from its $\omega$-cloud. Previous work on reconstructing $P$ from probes with the $\omega$-wedge required knowledge of the points of tangency between $P$ and the two rays of the $\omega$-wedge in addition to the location of the apex. Here we consider the setting where the maximal $\omega$-cloud alone is given. We give two conditions under which it uniquely defines $P$: (i) when $\omega < \pi$ is fixed/given, or (ii) when what is known is that $\omega < \pi/2$. We show that if neither of these two conditions hold, then $P$ may not be unique. We show that, when the uniqueness conditions hold, the polygon $P$ can be reconstructed in $O(n)$ time with $O(1)$ working space in addition to the input, where $n$ is the number of arcs in the input $\omega$-cloud.