Small grid embeddings of 3-polytopes (2009)
Mor, Ares Ribó, Rote, Günter, Schulz, André
We introduce an algorithm that embeds a given 3-connected planar graph as a convex 3-polytope with integer coordinates. The size of the coordinates is bounded by $O(2^{7.55n})=O(188^{n})$. If the...
Flip Graphs of Degree-Bounded (Pseudo-)Triangulations (2009)
Aichholzer, Oswin, Hackl, Thomas, Orden, David, Ramos, Pedro, Rote, Günter, Schulz, André, ...
We study flip graphs of (pseudo-)triangulations whose maximum vertex degree is bounded by a constant k. In particular, we consider (pseudo-)triangulations of sets of n points in convex position in...
Grammar-Based Design and Analysis of Technical Systems ∗ (2008)
ABSTRACT: Research on modeling and design of technical systems aims at a comprehensive system specification from different viewpoints and at different levels of granularity. Modern CASE tools (based...
Abstract Pointed Drawings of Planar Graphs (2008)
Oswin Aichholzer, Günter Rote, André Schulz, Birgit Vogtenhuber
We study the problem how to draw a planar graph such that every vertex is incident to an angle greater than π. In general a straight-line embedding cannot guarantee this property. We present...
Pointed Drawings of Planar Graphs (2008)
Oswin Aichholzer, Günter Rote, André Schulz, Birgit Vogtenhuber
We study the problem how to draw a planar graph such that every vertex is incident to an angle greater than π. In general a straightline embedding cannot guarantee this property. We present...
On rolling cube puzzles (2007)
Kevin Buchin, Maike Buchin, Erik D. Demaine, Martin L. Demaine, Dania El-khechen, Sándor P. Fekete, ...
We analyze the computational complexity of various rolling cube puzzles. 1
Threshold Arrangements and the Knapsack Problem (2005)
We show that a combinatorial question which has been studied in connection with lower bounds for the knapsack problem by Brimkov and Dantchev (2002) is related to threshold graphs, threshold...
Threshold Arrangements and the Knapsack Problem (2005)
We show that a combinatorial question which has been studied in connection with lower bounds for the knapsack problem by Brimkov and Dantchev (2002) is related to threshold graphs, threshold...
Threshold Arrangements and the Knapsack Problem (2005)
We show that a combinatorial question which has been studied in connection with lower bounds for the knapsack problem by Brimkov and Dantchev (2001) is related to threshold graphs, threshold...
On extreme points of the PPT Polytope (2004)
The polytope of pointed pseudo triangulations was described in [RSS01]. This polytope is a combinatorial tool to observe all possible pseudo triangulations of