10 citations · 18 across the 12 of their papers we have counts for
7 papers · 1 filter
Upward Point Set Embeddings of Paths and Trees
Elena Arseneva, Pilar Cano, Linda Kleist +4
We study upward planar straight-line embeddings (UPSE) of directed trees on given point sets. The given point set has size at least the number of vertices in the tree. For the…
Characterizing Universal Reconfigurability of Modular Pivoting Robots
Hugo A. Akitaya, Erik D. Demaine, Andrei Gonczi +7
We give both efficient algorithms and hardness results for reconfiguring between two connected configurations of modules in the hexagonal grid. The reconfiguration moves that we co…
Crossing-Optimal Extension of Simple Drawings
Robert Ganian, Thekla Hamm, Fabian Klute +2
In extension problems of partial graph drawings one is given an incomplete drawing of an input graph and is asked to complete the drawing while maintaining certain properties.…
Efficient Segment Folding is Hard
Takashi Horiyama, Fabian Klute, Matias Korman +3
We introduce a computational origami problem which we call the segment folding problem: given a set of line-segments in the plane the aim is to make creases along all segments…
Saturated -Plane Drawings with Few Edges
Fabian Klute, Irene Parada
A drawing of a graph is -plane if no edge is crossed more than times. In this paper we study saturated -plane drawings with few edges. This are -plane drawings in whic…
On the Maximum Number of Crossings in Star-Simple Drawings of with No Empty Lens
Stefan Felsner, Michael Hoffmann, Kristin Knorr +1
A star-simple drawing of a graph is a drawing in which adjacent edges do not cross. In contrast, there is no restriction on the number of crossings between two independent edges. W…
New Results in Sona Drawing: Hardness and TSP Separation
Man-Kwun Chiu, Erik D. Demaine, Jenny Diomidova +6
Given a set of point sites, a sona drawing is a single closed curve, disjoint from the sites and intersecting itself only in simple crossings, so that each bounded region of its co…