Andre Löffler

One-Bend Drawings of Outerplanar Graphs Inside Simple Polygons

Patrizio Angelini, Philipp Kindermann, Andre Löffler, Lena Schlipf et autres

We consider the problem of drawing an outerplanar graph with $n$ vertices with at most one bend per edge if the outer face is already drawn as a simple polygon. We prove that it can be decided in $O(nm)$ time if such …

Constrained Graph Layouts: Vertices on the Outer Face and on the Integer Grid

Andre Löffler

Constraining graph layouts - that is, restricting the placement of vertices and the routing of edges to obey certain constraints - is common practice in graph drawing. In this book, we discuss algorithmic results on two different restriction types: placing vertices on …

One-Bend Drawings of Outerplanar Graphs Inside Simple Polygons

Patrizio Angelini, Philipp Kindermann, Andre Löffler, Lena Schlipf et autres

it, de, gr (code pays fourni par la source)

Recognizing Stick Graphs with and without Length Constraints

Steven Chaplick, Philipp Kindermann, Andre Löffler, Florian Thiele et autres

Stick graphs are intersection graphs of horizontal and vertical line segments that all touch a line of slope $-1$ and lie above this line. De Luca et al. [De Luca et al. GD'18] considered the recognition problem of stick graphs when no …

de (code pays fourni par la source)

Recognizing Stick Graphs with and without Length Constraints

Steven Chaplick, Philipp Kindermann, Andre Löffler, Florian Thiele et autres

Stick graphs are intersection graphs of horizontal and vertical line segments that all touch a line of slope $-1$ and lie above this line. De Luca et al. [De Luca et al. GD'18] considered the recognition problem of stick graphs when no …

de (code pays fourni par la source)

Practical Topologically Safe Rounding of Geographic Networks

Thomas C. van Dijk, Andre Löffler

We consider the problem of accurately representing geographic networks at reduced coordinate precision. We require that vertices are placed on a grid and the network topology is retained, that is, we are not allowed to introduce intersections or collapse faces. Minimizing the …

de (code pays fourni par la source)

Stick Graphs with Length Constraints

Steven Chaplick, Andre Löffler, Florian Thiele, Alexander Wolff et autres

de (code pays fourni par la source)

Wüpstream

Thomas C. van Dijk, Tobias Greiner, Bas den Heijer, Nadja Henning et autres

This short paper describes Wüpstream, an efficient code for enumerating upstream features in undirected graphs. It uses a linear-time algorithm based on block-cut trees. We describe this algorithm and discuss some performance considerations in the C++ implementation. Code is available at: https://github.com/tcvdijk/wupstream.

de (code pays fourni par la source)

Planar Steiner Orientation is NP-complete

Moritz Beck, Johannes Blum, Myroslav Kryven, Andre Löffler et autres

Many applications in graph theory are motivated by routing or flow problems. Among these problems is Steiner Orientation: given a mixed graph G (having directed and undirected edges) and a set T of k terminal pairs in G, is there an orientation …

Beyond Outerplanarity

Steven Chaplick, Myroslav Kryven, Giuseppe Liotta, Andre Löffler et autres

de, it (code pays fourni par la source)

Beyond Outerplanarity

Steven Chaplick, Myroslav Kryven, Giuseppe Liotta, Andre Löffler et autres

We study straight-line drawings of graphs where the vertices are placed in convex position in the plane, i.e., \emph{convex drawings}. We consider two families of graph classes with convex drawings: \emph{outer $k$-planar} graphs, where each edge is crossed by at most $k$ …

Snapping Graph Drawings to the Grid Optimally

Andre Löffler, Thomas C. van Dijk, Alexander Wolff

In geographic information systems and in the production of digital maps for small devices with restricted computational resources one often wants to round coordinates to a rougher grid. This removes unnecessary detail and reduces space consumption as well as computation time. This …

de (code pays fourni par la source)