37 citations · 170 across the 24 of their papers we have counts for
31 papers
On Reconstructing a Convex Polygon from Partial Information
Alexander Baumann, Therese Biedl, Mahmoud Elashmawi +3
The reconstruction problem asks to construct a (convex) polygon that has a specified set of features, such as an ordered set of edge-lengths or an ordered set of polygon-angles. In…
Realizing Planar Linkages in Polygonal Domains
Thomas Depian, Carolina Haase, Martin Nöllenburg +1
A linkage consists of a graph and an edge-length function . Deciding whether can be realized as a planar straight-line embedding in $\ma…
Block Stacking, Airplane Refueling, and Robust Appointment Scheduling
Simon Gmeiner, Andreas S. Schulz
How can a stack of identical blocks be arranged to extend beyond the edge of a table as far as possible? We consider a generalization of this classic puzzle to blocks that differ i…
On plane cycles in geometric multipartite graphs
Marco Ricci, Jonathan Rollin, André Schulz +1
A geometric graph is a drawing of a graph in the plane where the vertices are drawn as points in general position and the edges as straight-line segments connecting their endpoints…
Reconfiguration of unit squares and disks: PSPACE-hardness in simple settings
Mikkel Abrahamsen, Kevin Buchin, Maike Buchin +5
We study two well-known reconfiguration problems. Given a start and a target configuration of geometric objects in a polygon, we wonder whether we can move the objects from the sta…
Side-Contact Representations with Convex Polygons in 3D: New Results for Complete Bipartite Graphs
André Schulz
A polyhedral surface~ in with convex polygons as faces is a side-contact representation of a graph~ if there is a bijection between the vertices of $…
On the geometric thickness of 2-degenerate graphs
Rahul Jain, Marco Ricci, Jonathan Rollin +1
A graph is 2-degenerate if every subgraph contains a vertex of degree at most 2. We show that every 2-degenerate graph can be drawn with straight lines such that the drawing decomp…
Arrangements of orthogonal circles with many intersections
Sarah Carmesin, André Schulz
An arrangement of circles in which circles intersect only in angles of is called an \emph{arrangement of orthogonal circles}. We show that in the case that no two circles are…
Adjacency Graphs of Polyhedral Surfaces
Elena Arseneva, Linda Kleist, Boris Klemz +4
We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in . We show that every graph is realizable as a p…
Augmenting Geometric Graphs with Matchings
Alexander Pilz, Jonathan Rollin, Lena Schlipf +1
We study noncrossing geometric graphs and their disjoint compatible geometric matchings. Given a cycle (a polygon) P we want to draw a set of pairwise disjoint straight-line edges…
The Number of Convex Polyominoes with Given Height and Width
Kevin Buchin, Man-Kwun Chiu, Stefan Felsner +2
We give a new combinatorial proof for the number of convex polyominoes whose minimum enclosing rectangle has given dimensions. We also count the subclass of these polyominoes that…
The Partition Spanning Forest Problem
Philipp Kindermann, Boris Klemz, Ignaz Rutter +2
Given a set of colored points in the plane, we ask if there exists a crossing-free straight-line drawing of a spanning forest, such that every tree in the forest contains exactly t…
Drawing Subcubic 1-Planar Graphs with Few Bends, Few Slopes, and Large Angles
Philipp Kindermann, Fabrizio Montecchiani, Lena Schlipf +1
We show that the 1-planar slope number of 3-connected cubic 1-planar graphs is at most 4 when edges are drawn as polygonal curves with at most 1 bend each. This bound is obtained b…
Lombardi Drawings of Knots and Links
Philipp Kindermann, Stephen Kobourov, Maarten Löffler +3
Knot and link diagrams are projections of one or more 3-dimensional simple closed curves into , such that no more than two points project to the same point in . These dia…
Experimental analysis of the accessibility of drawings with few segments
Philipp Kindermann, Wouter Meulemans, André Schulz
The visual complexity of a graph drawing is defined as the number of geometric objects needed to represent all its edges. In particular, one object may represent multiple edges, e.…
On Gallai's conjecture for series-parallel graphs and planar 3-trees
Philipp Kindermann, Lena Schlipf, André Schulz
A path cover is a decomposition of the edges of a graph into edge-disjoint simple paths. Gallai conjectured that every connected -vertex graph has a path cover with at most $\lc…
Drawing Planar Graphs with Few Geometric Primitives
Gregor Hültenschmidt, Philipp Kindermann, Wouter Meulemans +1
We define the \emph{visual complexity} of a plane graph drawing to be the number of basic geometric objects needed to represent all its edges. In particular, one object may represe…
On Minimizing Crossings in Storyline Visualizations
Irina Kostitsyna, Martin Nöllenburg, Valentin Polishchuk +2
In a storyline visualization, we visualize a collection of interacting characters (e.g., in a movie, play, etc.) by -monotone curves that converge for each interaction, and dive…
On Monotone Drawings of Trees
Philipp Kindermann, André Schulz, Joachim Spoerhase +1
A crossing-free straight-line drawing of a graph is monotone if there is a monotone path between any pair of vertices with respect to some direction. We show how to construct a mon…
Saturated simple and 2-simple topological graphs with few edges
Péter Hajnal, Alexander Igamberdiev, Günter Rote +1
A simple topological graph is a topological graph in which any two edges have at most one common point, which is either their common endpoint or a proper crossing. More generally,…
Contact Representations of Sparse Planar Graphs
Md. Jawaherul Alam, David Eppstein, Michael Kaufmann +4
We study representations of graphs by contacts of circular arcs, CCA-representations for short, where the vertices are interior-disjoint circular arcs in the plane and each edge is…
Counting Carambolas
Adrian Dumitrescu, Maarten Löffler, André Schulz +1
We give upper and lower bounds on the maximum and minimum number of geometric configurations of various kinds present (as subgraphs) in a triangulation of points in the plane.…
Embedding Stacked Polytopes on a Polynomial-Size Grid
Erik D. Demaine, Andre Schulz
A stacking operation adds a -simplex on top of a facet of a simplicial -polytope while maintaining the convexity of the polytope. A stacked -polytope is a polytope that is…
A Duality Transform for Constructing Small Grid Embeddings of 3d Polytopes
Alexander Igamberdiev, André Schulz
We study the problem of how to obtain an integer realization of a 3d polytope when an integer realization of its dual polytope is given. We focus on grid embeddings with small coor…