12 citations · 38 across the 11 of their papers we have counts for
18 papers
Point Set Embeddability with List Constraints
Thomas Depian, Joseph Dorfer, Boris Klemz +2
Deciding whether a given graph admits a planar straight-line drawing where each vertex is placed on some point from a given finite point set is known as Point Set Embeddability and…
Constrained Level Planarity is FPT with Respect to the Vertex Cover Number
Boris Klemz, Marie Diana Sieper
The problem Level Planarity asks for a crossing-free drawing of a graph in the plane such that vertices are placed at prescribed y-coordinates (called levels) and such that every e…
Constrained and Ordered Level Planarity Parameterized by the Number of Levels
Václav Blažej, Boris Klemz, Felix Klesen +3
The problem Level Planarity asks for a crossing-free drawing of a graph in the plane such that vertices are placed at prescribed y-coordinates (called levels) and such that every e…
Deciding the Feasibility and Minimizing the Height of Tangles
Oksana Firman, Philipp Kindermann, Boris Klemz +3
We study the following combinatorial problem. Given a set of y-monotone \emph{wires}, a \emph{tangle} determines the order of the wires on a number of horizontal \emph{layers}…
Morphing Graph Drawings in the Presence of Point Obstacles
Oksana Firman, Tim Hegemann, Boris Klemz +4
A crossing-free morph is a continuous deformation between two graph drawings that preserves straight-line pairwise noncrossing edges. Motivated by applications in 3D morphing probl…
The Density Formula: One Lemma to Bound Them All
Michael Kaufmann, Boris Klemz, Kristin Knorr +3
We introduce the Density Formula for (topological) drawings of graphs in the plane or on the sphere, which relates the number of edges, vertices, crossings, and sizes of cells in t…
Outside-Obstacle Representations with All Vertices on the Outer Face
Oksana Firman, Philipp Kindermann, Jonathan Klawitter +3
An obstacle representation of a graph consists of a set of polygonal obstacles and a drawing of as a visibility graph with respect to the obstacles: vertices are mapped to…
The Segment Number: Algorithms and Universal Lower Bounds for Some Classes of Planar Graphs
Ina Goeßmann, Jonathan Klawitter, Boris Klemz +5
The segment number of a planar graph is the smallest number of line segments needed for a planar straight-line drawing of . Dujmović, Eppstein, Suderman, and Wood [CGTA'07]…
Simplifying Non-Simple Fan-Planar Drawings
Boris Klemz, Kristin Knorr, Meghana M. Reddy +1
A drawing of a graph is fan-planar if the edges intersecting a common edge share a vertex on the same side of . More precisely, orienting arbitrarily and the other e…
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…
The Complexity of Finding Tangles
Oksana Firman, Philipp Kindermann, Boris Klemz +3
We study the following combinatorial problem. Given a set of y-monotone curves, which we call wires, a tangle determines the order of the wires on a number of horizontal layers…
On the edge-vertex ratio of maximal thrackles
Oswin Aichholzer, Linda Kleist, Boris Klemz +2
A drawing of a graph in the plane is a thrackle if every pair of edges intersects exactly once, either at a common vertex or at a proper crossing. Conway's conjecture states that a…
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…
Convexity-Increasing Morphs of Planar Graphs
Linda Kleist, Boris Klemz, Anna Lubiw +3
We study the problem of convexifying drawings of planar graphs. Given any planar straight-line drawing of an internally 3-connected graph, we show how to morph the drawing to one w…
Linear-Time Algorithms for Maximum-Weight Induced Matchings and Minimum Chain Covers in Convex Bipartite Graphs
Boris Klemz, Günter Rote
A bipartite graph is convex if the vertices in can be linearly ordered such that for each vertex , the neighbors of are consecutive in the ordering of $…
Ordered Level Planarity, Geodesic Planarity and Bi-Monotonicity
Boris Klemz, Günter Rote
We introduce and study the problem Ordered Level Planarity which asks for a planar drawing of a graph such that vertices are placed at prescribed positions in the plane and such th…
Strongly Monotone Drawings of Planar Graphs
Stefan Felsner, Alexander Igamberdiev, Philipp Kindermann +3
A straight-line drawing of a graph is a monotone drawing if for each pair of vertices there is a path which is monotonically increasing in some direction, and it is called a strong…
Recognizing Weighted Disk Contact Graphs
Boris Klemz, Martin Nöllenburg, Roman Prutkin
Disk contact representations realize graphs by mapping vertices bijectively to interior-disjoint disks in the plane such that two disks touch each other if and only if the correspo…