Article in journal, newspaper, or magazine
[
to top
]

Angelini, P., Bekos, M., Didimo, W., Grilli, L., Kindermann, P., Mchedlidze, T., Prutkin, R., Symvonis, A., Tappini, A.: Greedy Rectilinear Drawings. Theoretical Computer Science. (2019).
A drawing of a graph is greedy if for each ordered pair of vertices \($u$\) and \($v$\), there is a path from \($u$\) to \($v$\) such that the Euclidean distance to \($v$\) decreases monotonically at every vertex of the path. The existence of greedy drawings has been widely studied under different topological and geometric constraints, such as planarity, face convexity, and drawing succinctness. We introduce greedy rectilinear drawings, in which each edge is either a horizontal or a vertical segment. These drawings have several properties that improve human readability and support network routing. We address the problem of testing whether a planar rectilinear representation, i.e., a plane graph with specified vertex angles, admits vertex coordinates that define a greedy drawing. We provide a characterization, a lineartime testing algorithm, and a full generative scheme for universal greedy rectilinear representations, i.e., those for which every drawing is greedy. For general greedy rectilinear representations, we give a combinatorial characterization and, based on it, a polynomialtime testing and drawing algorithm for a meaningful subset of instances.

Kindermann, P., Kobourov, S., Löffler, M., Nöllenburg, M., Schulz, A., Vogtenhuber, B.: Lombardi Drawings of Knots and Links. Journal of Computational Geometry. (2019).
Knot and link diagrams are projections of one or more 3dimensional simple closed curves into \($R^2$\), such that no more than two points project to the same point in \($R^2$\). These diagrams are drawings of 4regular plane multigraphs. Knots are typically smooth curves in \($R^3$\), so their projections should be smooth curves in \($R^2$\) with good continuity and large crossing angles: exactly the properties of Lombardi graph drawings (defined by circulararc edges and perfect angular resolution). We show that several knots do not allow Lombardi drawings. On the other hand, we identify a large class of 4regular plane multigraphs that do have Lombardi drawings. We then study two relaxations of Lombardi drawings and show that every knot admits a plane 2Lombardi drawing (where edges are composed of two circular arcs). Further, every knot is emphnearLombardi, that is, it can be drawn as Lombardi drawing when relaxing the angular resolution requirement by an arbitrary small angular offset \($\eps$\), while maintaining a \($180^\circ$\) angle between opposite edges.

Eppstein, D., Kindermann, P., Kobourov, S., Liotta, G., Lubiw, A., Maignan, A., Mondal, D., Vosoughpour, H., Whitesides, S., Wismath, S.: On the Planar Split Thickness of Graphs. Algorithmica. 80, 977994 (2018).
Motivated by applications in graph drawing and information visualization, we examine the planar split thickness of a graph, that is, the smallest \($k$\) such that the graph is \($k$\)splittable into a planar graph. A \($k$\)split operation substitutes a vertex \($v$\) by at most \($k$\) new vertices such that each neighbor of \($v$\) is connected to at least one of the new vertices. We first examine the planar split thickness of complete and complete bipartite graphs. We then prove that it is NPhard to recognize graphs that are 2splittable into a planar graph, and show that one can approximate the planar split thickness of a graph within a constant factor. If the treewidth is bounded, then we can even verify \($k$\)splittablity in linear time, for a constant \($k$\).

Angelini, P., Bekos, M.A., Kaufmann, M., Kindermann, P., Schneck, T.: 1FanBundlePlanar Drawings of Graphs. Theoretical Computer Science. 723, 2350 (2018).
Edge bundling is an important concept heavily used for graph visualization purposes. To enable the comparison with other established nearlyplanarity models in graph drawing, we formulate a new edgebundling model which is inspired by the recently introduced fanplanar graphs. In particular, we restrict the bundling to the endsegments of the edges. As in 1planarity, we call our model emph1fanbundleplanarity, as we allow at most one crossing per bundle. For the two variants where we allow either one or, more naturally, both endsegments of each edge to be part of bundles, we present edge density results and consider various recognition questions, not only for general graphs, but also for the outer and 2layer variants. We conclude with a series of challenging questions.

Kindermann, P., Meulemans, W., Schulz, A.: Experimental analysis of the accessibility of drawings with few segments. Journal of Graph Algorithms and Applications. 22, 501518 (2018).
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.g., one needs only one line segment to draw two collinear incident edges. We study the question if drawings with few segments have a better aesthetic appeal and help the user to asses the underlying graph. We design an experiment that investigates two different graph types (trees and sparse graphs), three different layout algorithms for trees, and two different layout algorithms for sparse graphs. We asked the users to give an aesthetic ranking on the layouts and to perform a furthestpair or shortestpath task on the drawings.

Alt, H., Buchin, K., Chaplick, S., Cheong, O., Kindermann, P., Knauer, C., Stehn, F.: Placing your Coins on a Shelf. Journal of Computational Geometry. 9, 312327 (2018).
We consider the problem of packing a family of disks "on a shelf", that is, such that each disk touches the \($x$\)axis from above and such that no two disks overlap. We prove that the problem of minimizing the distance between the leftmost point and the rightmost point of any disk is NPhard. On the positive side, we show how to approximate this problem within a factor of 4/3 in \($O(n \log n)$\) time, and provide an \($O(n \log n)$\)time exact algorithm for a special case, in particular when the ratio between the largest and smallest radius is at most four.

Angelini, P., Lozzo, G.D., Battista, G.D., Donato, V.D., Kindermann, P., Rote, G., Rutter, I.: Windrose Planarity: Embedding Graphs with DirectionConstrained Edges. Transactions on Algorithms. 14, 54:154:24 (2018).
Given a planar graph \($G=(V,E)$\) and a partition of the neighbors of each vertex \($v \in V$\) in four sets \($UR(v)$\), \($UL(v)$\), \($DL(v)$\), and \($DR(v)$\), the problem Windrose Planarity asks to decide whether \($G$\) admits a emphwindroseplanar drawing, that is, a planar drawing in which (i) each neighbor \($u in UR(v)$\) is above and to the right of \($v$\), (ii) each neighbor \($u in UL(v)$\) is above and to the left of \($v$\), (iii) each neighbor \($u in DL(v)$\) is below and to the left of \($v$\), (iv) each neighbor \($u in DR(v)$\) is below and to the right of \($v$\), and (v) edges are represented by curves that are monotone with respect to each axis. By exploiting both the horizontal and the vertical relationship among vertices, windroseplanar drawings allow to simultaneously visualize two partial orders defined by means of the edges of the graph. Although the problem is NPhard in the general case, we give a polynomialtime algorithm for testing whether there exists a windroseplanar drawing that respects a combinatorial embedding that is given as part of the input. This algorithm is based on a characterization of the plane triangulations admitting a windroseplanar drawing. Furthermore, for any embedded graph admitting a windroseplanar drawing we show how to construct one with at most one bend per edge on an \($O(n) times O(n)$\) grid. The latter result contrasts with the fact that straightline windroseplanar drawings may require exponential area.

Hültenschmidt, G., Kindermann, P., Meulemans, W., Schulz, A.: Drawing Planar Graphs with Few Geometric Primitives. Journal of Graph Algorithms and Applications. 22, 357387 (2018).
We define the emphvisual complexity of a plane graph drawing to be the number of geometric objects needed to represent all its edges. In particular, one object may represent multiple edges (e.g. you need only one line segment to draw two collinear edges of the same vertex). We show that trees can be drawn with \($3n/4$\) straightline segments on a polynomial grid, and with \($n/2$\) straightline segments on a quasipolynomial grid. We also study the problem of drawing maximal triangulations with circular arcs and provide an algorithm to draw such graphs using only \($(5n  11)/3$\) arcs. This provides a significant improvement over the lower bound of \($2n$\) for line segments for a nontrivial graph class.

Bekos, M.A., van Dijk, T.C., Fink, M., Kindermann, P., Kobourov, S., Pupyrev, S., Spoerhase, J., Wolff, A.: Improved Approximation Algorithms for Box Contact Representations. Algorithmica. 77, 902920 (2017).
We study the following geometric representation problem: Given a graph whose vertices correspond to axisaligned rectangles with fixed dimensions, arrange the rectangles without overlaps in the plane such that two rectangles touch if the graph contains an edge between them. This problem is called textscContact Representation of Word Networks (\textscCrown) since it formalizes the geometric problem behind drawing word clouds in which semantically related words are close to each other. textscCrown is known to be NPhard, and there are approximation algorithms for certain graph classes for the optimization version, textscMaxCrown, in which realizing each desired adjacency yields a certain profit. We present the first \($O(1)$\)approximation algorithm for the general case, when the input is a complete weighted graph, and for the bipartite case. Since the subgraph of realized adjacencies is necessarily planar, we also consider several planar graph classes (namely stars, trees, outerplanar, and planar graphs), improving upon the known results. For some graph classes, we also describe improvements in the unweighted case, where each adjacency yields the same profit. Finally, we show that the problem is APXhard on bipartite graphs of bounded maximum degree.

Bekos, M.A., van Dijk, T.C., Kindermann, P., Wolff, A.: Simultaneous Drawing of Planar Graphs with Right–Angle Crossings and Few Bends. Journal of Graph Algorithms and Applications. 20, 133158 (2016).
Given two planar graphs that are defined on the same set of vertices, a RAC simultaneous drawing is one in which each graph is drawn planar, there are no edge overlaps and the crossings between the two graphs form right angles. The geometric version restricts the problem to straightline drawings. It is known, however, that there exists a wheel and a matching which do not admit a geometric RAC simultaneous drawing. In order to enlarge the class of graphs that admit RAC simultaneous drawings, we allow bends in the resulting drawings. We prove that two planar graphs always admit a RAC simultaneous drawing with six bends per edge each, in quadratic area. For more restricted classes of planar graphs (i.e., matchings, paths, cycles, outerplanar graphs and subhamiltonian graphs), we manage to significantly reduce the required number of bends per edge, while keeping the area quadratic.

Brandenburg, F.J., Didimo, W., Evans, W.S., Kindermann, P., Liotta, G., Montecchiani, F.: Recognizing and Drawing ICPlanar Graphs. Theoretical Computer Science. 636, 116 (2016).
ICplanar graphs are those graphs that admit a drawing where no two crossed edges share an endvertex and each edge is crossed at most once. They are a proper subfamily of the 1planar graphs. Given an embedded ICplanar graph \($G$\) with \($n$\) vertices, we present an \($O(n)$\)time algorithm that computes a straightline drawing of \($G$\) in quadratic area, and an \($O(n^3)$\)time algorithm that computes a straightline drawing of \($G$\) with rightangle crossings in exponential area. Both these area requirements are worstcase optimal. We also show that it is NPcomplete to test ICplanarity both in the general case and in the case in which a rotation system is fixed for the input graph. Furthermore, we describe a polynomialtime algorithm to test whether a set of matching edges can be added to a triangulated planar graph such that the resulting graph is ICplanar.

Kindermann, P., Niedermann, B., Rutter, I., Schaefer, M., Schulz, A., Wolff, A.: MultiSided Boundary Labeling. Algorithmica. 76, 225258 (2016).
In the Boundary Labeling problem, we are given a set of \($n$\) points, referred to as sites, inside an axisparallel rectangle \($R$\), and a set of \($n$\) pairwise disjoint rectangular labels that are attached to \($R$\) from the outside. The task is to connect the sites to the labels by nonintersecting rectilinear paths, socalled leaders, with at most one bend. In this paper, we study the MultiSided Boundary Labeling problem, with labels lying on at least two sides of the enclosing rectangle. We present a polynomialtime algorithm that computes a crossingfree leader layout if one exists. So far, such an algorithm has only been known for the cases in which labels lie on one side or on two opposite sides of \($R$\) (here a crossingfree solution always exists). The case where labels may lie on adjacent sides is more difficult. We present efficient algorithms for testing the existence of a crossingfree leader layout that labels all sites and also for maximizing the number of labeled sites in a crossingfree leader layout. For twosided boundary labeling with adjacent sides, we further show how to minimize the total leader length in a crossingfree layout.
Article in Conference Proceedings
[
to top
]

Kindermann, P., Mchedlidze, T., Meulemans, W., Rutter, I.: Graph Drawing Contest Report. In: Auber, D. and Valtr, P. (eds.) Proc. 28th International Symposium on Graph Drawing and Network Visualization (GD'20) (2020).

Biedl, T., Biniaz, A., Irvine, V., Jain, K., Kindermann, P., Lubiw, A.: Maximum Matchings and Minimum Blocking Sets in \($\Theta_6$\)Graphs. In: Sau, I. and Thilikos, D.M. (eds.) Proceedings of the 45th International Workshop on GraphTheoretic Concepts in Computer Science (WG'19). p. 258270. SpringerVerlag (2019).
Theta_6graphs are important geometric graphs that have many applications. They are equivalent to Delaunay graphs where empty equilateral triangles with a horizontal edge take the place of empty circles. We investigate lower bounds on the size of maximum matchings in these graphs. The best known lower bound is (n1)/3, where n is the number of vertices of the graph. Babu et al. (2014) conjectured that any Theta_6graph has a perfect matching (as is true for standard Delaunay graphs). Although this conjecture remains open, we improve the lower bound to (3n8)/7. We also relate the size of maximum matchings in Theta_6graphs to the minimum size of a blocking set. Every edge of a Theta_6graph on a point set P corresponds to an empty triangle that contains the endpoints of the edge but no other point of P. A blocking set has at least one point in each such triangle. We prove that the size of a maximum matching is at least b(n)/2 where b(n) is the minimum, over all Theta_6graphs with n vertices, of the minimum size of a blocking set. In the other direction, lower bounds on matchings allow us to show that b(n) >= 3n/4  2.

Firman, O., Kindermann, P., Ravsky, A., Wolff, A., Zink, J.: Computing Optimal Tangles Faster. In: Löffler, M. (ed.) Proceedings of the 35th European Workshop on Computational Geometry (EuroCG'19). Utrecht (2019).
We study the following combinatorial problem. Given a set of n ymonotone wires, a tangle determines the order of the wires on a number of horizontal layers such that the orders of the wires on any two consecutive layers differ only in swaps of neighboring wires. Given a multiset L of swaps (that is, unordered pairs of numbers between 1 and n) and an initial order of the wires, a tangle realizes L if each pair of wires changes its order exactly as many times as specified by L. The aim is to find a tangle that realizes L using the smallest number of layers. We show that this problem is NPhard, and we give an algorithm that computes an optimal tangle for n wires and a given list L of swaps in O((2L/n^2+1)^(n^2/2)phi^n n) time, where phi~1.618 is the golden ratio. We can treat lists where every swap occurs at most once in O(n! phi^n) time. We implemented the algorithm for the general case and compared it to an existing algorithm.

Biedl, T., Biniaz, A., Irvine, V., Jain, K., Kindermann, P., Lubiw, A.: Maximum Matchings and Minimum Blocking Sets in \($\Theta_6$\)Graphs. In: Löffler, M. (ed.) Proceedings of the 35th European Workshop on Computational Geometry (EuroCG'19). Utrecht (2019).
Theta_6graphs are important geometric graphs that have many applications. They are equivalent to Delaunay graphs where empty equilateral triangles with a horizontal edge take the place of empty circles. We investigate lower bounds on the size of maximum matchings in these graphs. The best known lower bound is (n1)/3, where n is the number of vertices of the graph. Babu et al. (2014) conjectured that any Theta_6graph has a perfect matching (as is true for standard Delaunay graphs). Although this conjecture remains open, we improve the lower bound to (3n8)/7. We also relate the size of maximum matchings in Theta_6graphs to the minimum size of a blocking set. Every edge of a Theta_6graph on a point set P corresponds to an empty triangle that contains the endpoints of the edge but no other point of P. A blocking set has at least one point in each such triangle. We prove that the size of a maximum matching is at least b(n)/2 where b(n) is the minimum, over all Theta_6graphs with n vertices, of the minimum size of a blocking set. In the other direction, lower bounds on matchings allow us to show that b(n) >= 3n/4  2.

Chimani, M., Kindermann, P., Montecchiani, F., Valtr, P.: Crossing Numbers of BeyondPlanar Graphs. In: Archambault, D. and Tóth, C.D. (eds.) Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD'19). SpringerVerlag (2019).
We study lower bounds on the minimum number of crossings for 1planar, quasiplanar, and fanplanar graphs. We prove that there are nvertex 1planar (quasiplanar, fanplanar) graphs such that any 1planar (quasiplanar, fanplanar) drawing has Omega(n) crossings, while O(1) crossings suffice in a crossingminimal drawing with no restrictions on local edge crossing patterns.

Biedl, T., Kindermann, P.: Finding Tutte Paths in Linear Time. In: Baier, C., Chatzigiannakis, I., Flocchini, P., and Leonardi, S. (eds.) Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP'19). p. 23:123:14. Schloss Dagstuhl  LeibnizZentrum fuer Informatik (2019).
It is wellknown that every planar graph has a Tutte path, i.e., a path P such that any component of GP has at most three attachment points on P. However, it was only recently shown that such Tutte paths can be found in polynomial time. In this paper, we give a new proof that 3connected planar graphs have Tutte paths, which leads to a lineartime algorithm to find Tutte paths. Furthermore, our Tutte path has special properties: it visits all exterior vertices, all components of GP have exactly three attachment points, and we can assign distinct representatives to them that are interior vertices. Finally, our running time bound is slightly stronger; we can bound it in terms of the degrees of the faces that are incident to P. This allows us to find some applications of Tutte paths (such as binary spanning trees and 2walks) in linear time as well.

Chaplick, S., Kindermann, P., Löffler, A., Thiele, F., Wolff, A., Zaft, A., Zink, J.: Stick Graphs with Length Constraints. In: Archambault, D. and Tóth, C.D. (eds.) Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD'19). SpringerVerlag (2019).
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. [GD’18] considered the recognition problem of stick graphs when no order is given (STICK), when the order of either one of the two sets is given (STICK_A), and when the order of both sets is given (STICK_AB). They showed how to solve STICK_AB efficiently. In this paper, we improve the running time of their algorithm, and we solve STICK_A efficiently. Further, we consider variants of these problems where the lengths of the sticks are given as input. We show that these variants of STICK, STICK_A , and STICK_AB are all NPcomplete. On the positive side, we give an efficient solution for STICK_AB with fixed stick lengths if there are no isolated vertices.

Firman, O., Kindermann, P., Ravsky, A., Wolff, A., Zink, J.: Computing HeightOptimal Tangles Faster. In: Archambault, D. and Tóth, C.D. (eds.) Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD'19). SpringerVerlag (2019).
We study the following combinatorial problem. Given a set of n ymonotone wires, a tangle determines the order of the wires on a number of horizontal layers such that the orders of the wires on any two consecutive layers differ only in swaps of neighboring wires. Given a multiset L of swaps (that is, unordered pairs of numbers between 1 and n) and an initial order of the wires, a tangle realizes L if each pair of wires changes its order exactly as many times as specified by L. The aim is to find a tangle that realizes L using the smallest number of layers. We show that this problem is NPhard, and we give an algorithm that computes an optimal tangle for n wires and a given list L of swaps in O((2L/n^2+1)^(n^2/2)phi^n n) time, where phi~1.618 is the golden ratio. We can treat lists where every swap occurs at most once in O(n! phi^n) time. We implemented the algorithm for the general case and compared it to an existing algorithm.

Firman, O., Kindermann, P., Ravsky, A., Wolff, A., Zink, J.: Computing Optimal Tangles Faster. In: Cheng, S.W. (ed.) Proceedings of the 12th Annual Meeting of the Asian Association for Algorithms and Computation (AAAC'19). Seoul (2019).
We study the following combinatorial problem. Given a set of n ymonotone wires, a tangle determines the order of the wires on a number of horizontal layers such that the orders of the wires on any two consecutive layers differ only in swaps of neighboring wires. Given a multiset L of swaps (that is, unordered pairs of numbers between 1 and n) and an initial order of the wires, a tangle realizes L if each pair of wires changes its order exactly as many times as specified by L. The aim is to find a tangle that realizes L using the smallest number of layers. We show that this problem is NPhard, and we give an algorithm that computes an optimal tangle for n wires and a given list L of swaps in O((2L/n^2+1)^(n^2/2)phi^n n) time, where phi~1.618 is the golden ratio. We can treat lists where every swap occurs at most once in O(n! phi^n) time. We implemented the algorithm for the general case and compared it to an existing algorithm.

Kindermann, P., Mchedlidze, T., Schneck, T., Symvonis, A.: Drawing Planar Graphs with Few Segments on a Polynomial Grid. In: Archambault, D. and Tóth, C.D. (eds.) Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD'19). SpringerVerlag (2019).
The visual complexity of a graph drawing can be measured by the number of geometric objects used for the representation of its elements. In this paper, we study planar graph drawings where edges are represented by few segments. In such a drawing, one segment may represent multiple edges forming a path. Drawings of planar graphs with few segments were intensively studied in the past years. However, the area requirements were only considered for limited subclasses of planar graphs. In this paper, we show that trees have drawings with 3n/41 segments and n^2 area, improving the previous result of O(n^3.58). We also show that 3connected planar graphs and biconnected outerplanar graphs have a drawing with 8n/3O(1) and 3n/2O(1) segments, respectively, and O(n^3) area.

Kindermann, P., Mchedlidze, T., Rutter, I.: Graph Drawing Contest Report. In: Archambault, D. and Tóth, C.D. (eds.) Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD'19). SpringerVerlag (2019).

Devanny, W., Kindermann, P., Löffler, M., Rutter, I.: Graph Drawing Contest Report. In: Biedl, T. and Kerren, A. (eds.) Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD'18). p. 609617. SpringerVerlag (2018).

Kindermann, P., Klemz, B., Rutter, I., Schnider, P., Schulz, A.: The Partition Spanning Forest Problem. In: Mulzer, W. (ed.) Proceedings of the 34th European Workshop on Computational Geometry (EuroCG'18). p. 53:153:6. FU Berlin (2018).
Given a set of colored points in the plane, we ask if there exists a crossingfree straightline drawing of a spanning forest, such that every tree in the forest contains exactly the points of one color class. We show that the problem is NPcomplete, even if every color class contains at most five points, but it is solvable in \($O(n^2)$\) time when each color class contains at most three points. If we require that the spanning forest is a linear forest, then the problem becomes NPcomplete even if every color class contains at most four points.

Biedl, T., Biniaz, A., Irvine, V., Kindermann, P., Naredla, A.M., Turcotte, A.: Integral Unit BarVisibility Graphs. In: Durocher, S. and Kamali, S. (eds.) Proceedings of the 30th Canadian Conference on Computational Geometry (CCCG'18). p. 230246. University of Manitoba (2018).
In this paper, we take another look at unit barvisibility representations, that is barvisibility representations where every bar has the same width. Motivated by some applications in textile construction, we restrict the graphs further to integral unit barvisibility representations (IUBVR), that is a barvisibility representation where the bar of every vertex is a horizontal line segment [i1,i], for some positive integer i, at some realvalue y position. We study which graph classes do/don't have an IUBVR, both in the weak model and in the strong model. In the weak model, we show that it is NPhard to test whether a graph has an IUBVR. We also present recursive algorithms to create IUBVRs for some graph classes, such as 2connected outerplanar graphs with maximum degree 4. In the strong model, we provide a polynomialtime algorithm to test for the existence of a strong IUBVR. In the event of a positive answer, the algorithm also generates such a strong IUBVR.

Angelini, P., Bekos, M., Didimo, W., Grilli, L., Kindermann, P., Mchedlidze, T., Prutkin, R., Symvonis, A., Tappini, A.: Greedy Rectilinear Drawings. In: Biedl, T. and Kerren, A. (eds.) Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD'18). p. 495508. SpringerVerlag (2018).
A drawing of a graph is greedy if for each ordered pair of vertices \($u$\) and \($v$\), there is a path from \($u$\) to \($v$\) such that the Euclidean distance to \($v$\) decreases monotonically at every vertex of the path. The existence of greedy drawings has been widely studied under different topological and geometric constraints, such as planarity, face convexity, and drawing succinctness. We introduce greedy rectilinear drawings, in which each edge is either a horizontal or a vertical segment. These drawings have several properties that improve human readability and support network routing. We address the problem of testing whether a planar rectilinear representation, i.e., a plane graph with specified vertex angles, admits vertex coordinates that define a greedy drawing. We provide a characterization, a lineartime testing algorithm, and a full generative scheme for universal greedy rectilinear representations, i.e., those for which every drawing is greedy. For general greedy rectilinear representations, we give a combinatorial characterization and, based on it, a polynomialtime testing and drawing algorithm for a meaningful subset of instances.

Kindermann, P., Montecchiani, F., Schlipf, L., Schulz, A.: Drawing Subcubic 1Planar Graphs with Few Bends, Few Slopes, and Large Angles. In: Biedl, T. and Kerren, A. (eds.) Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD'18). p. 152166. SpringerVerlag (2018).
We show that the 1planar slope number of 3connected cubic 1planar graphs is at most 4 when edges are drawn as polygonal curves with at most one bend per edge. This bound is obtained with drawings whose vertex and crossing resolution is at least pi/4. On the other hand, there is an embedding of a graph that needs 3 slopes when drawn with 1bend edges. We also show that two slopes always suffice for 1planar drawings of subcubic 1planar graphs with at most two bends per edge. This bound is obtained with vertex and crossing resolution pi/2. For straightline drawings of 1plane graphs, we present lower bounds for the 1planar slope number in terms of the number of vertices and of the maximum degree.

Kindermann, P., Kobourov, S., Löffler, M., Nöllenburg, M., Schulz, A., Vogtenhuber, B.: Lombardi Drawings of Knots and Links. In: Frati, F. and Ma, K.L. (eds.) Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD'17). p. 113126. Springer (2017).
Knot and link diagrams are projections of one or more 3dimensional simple closed curves into \($R^2$\), such that no more than two points project to the same point in \($R^2$\). These diagrams are drawings of 4regular plane multigraphs. Knots are typically smooth curves in \($R^3$\), so their projections should be smooth curves in \($R^2$\) with good continuity and large crossing angles: exactly the properties of Lombardi graph drawings (defined by circulararc edges and perfect angular resolution). We show that several knots do not allow Lombardi drawings. On the other hand, we identify a large class of 4regular plane multigraphs that do have Lombardi drawings. We then study two relaxations of Lombardi drawings and show that every knot admits a plane 2Lombardi drawing (where edges are composed of two circular arcs). Further, every knot is nearLombardi, that is, it can be drawn as Lombardi drawing when relaxing the angular resolution requirement by an arbitrary small angular offset \($\epsilon$\), while maintaining a \($180^\circ$\) angle between opposite edges.

Kindermann, P., Meulemans, W., Schulz, A.: Experimental analysis of the accessibility of drawings with few segments. In: Frati, F. and Ma, K.L. (eds.) Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD'17). p. 5264. SpringerVerlag (2017).
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.g., one needs only one line segment to draw two collinear incident edges. We study the question if drawings with few segments have a better aesthetic appeal and help the user to asses the underlying graph. We design an experiment that investigates two different graph types (trees and sparse graphs), three different layout algorithms for trees, and two different layout algorithms for sparse graphs. We asked the users to give an aesthetic ranking on the layouts and to perform a furthestpair or shortestpath task on the drawings.

Devanny, W., Kindermann, P., Löffler, M., Rutter, I.: Graph Drawing Contest Report. In: Frati, F. and Ma, K.L. (eds.) Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD'17). p. 575582. SpringerVerlag (2017).

Alt, H., Buchin, K., Chaplick, S., Cheong, O., Kindermann, P., Knauer, C., Stehn, F.: Placing your Coins on a Shelf. In: Okamoto, Y. and Tokuyama, T. (eds.) Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC'17). p. 4:14:12. Schloss Dagstuhl  LeibnizZentrum fuer Informatik (2017).
We consider the problem of packing a family of disks "on a shelf", that is, such that each disk touches the \($x$\)axis from above and such that no two disks overlap. We prove that the problem of minimizing the distance between the leftmost point and the rightmost point of any disk is NPhard. On the positive side, we show how to approximate this problem within a factor of 4/3 in \($O(n \log n)$\) time, and provide an \($O(n \log n)$\)time exact algorithm for a special case, in particular when the ratio between the largest and smallest radius is at most four.

Hültenschmidt, G., Kindermann, P., Meulemans, W., Schulz, A.: Drawing Planar Graphs with Few Geometric Primitives. In: Bodlaender, H.L. and Woeginger, G.J. (eds.) Proceedings of the 43rd International Workshop on GraphTheoretic Concepts in Computer Science (WG'17). p. 316329. SpringerVerlag (2017).
We define the visual complexity of a plane graph drawing to be the number of geometric objects needed to represent all its edges. In particular, one object may represent multiple edges (e.g. you need only one line segment to draw two collinear edges of the same vertex). We show that trees can be drawn with \($3n/4$\) straightline segments on a polynomial grid, and with \($n/2$\) straightline segments on a quasipolynomial grid. We also study the problem of drawing maximal triangulations with circular arcs and provide an algorithm to draw such graphs using only \($(5n  11)/3$\) arcs. This provides a significant improvement over the lower bound of \($2n$\) for line segments for a nontrivial graph class.

Angelini, P., Bekos, M.A., Kaufmann, M., Kindermann, P., Schneck, T.: 1FanBundlePlanar Drawings of Graphs. In: Frati, F. and Ma, K.L. (eds.) Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD'17). p. 517530. SpringerVerlag (2017).
Edge bundling is an important concept heavily used for graph visualization purposes. To enable the comparison with other established nearlyplanarity models in graph drawing, we formulate a new edgebundling model which is inspired by the recently introduced fanplanar graphs. In particular, we restrict the bundling to the endsegments of the edges. As in 1planarity, we call our model 1fanbundleplanarity, as we allow at most one crossing per bundle. For the two variants where we allow either one or, more naturally, both endsegments of each edge to be part of bundles, we present edge density results and consider various recognition questions, not only for general graphs, but also for the outer and 2layer variants. We conclude with a series of challenging questions.

Angelini, P., Da Lozzo, G., Di Battista, G., Di Donato, V., Kindermann, P., Rote, G., Rutter, I.: Windrose Planarity – Embedding Graphs with DirectionConstrained Edges. In: Krauthgamer, R. (ed.) Proceedings of the 27th Annual ACMSIAM Symposium on Discrete Algorithms (SODA'16). p. 985996. SIAM (2016).
Given a planar graph G(V,E) and a partition of the neighbors of each vertex v in V in four sets Nur(v), Nul(v), Ndl(v), and Ndr(v), the problem Windrose Planarity asks to decide whether G admits a windroseplanar drawing, that is, a planar drawing in which (i) each neighbor u in Nur(v) is above and to the right of v, (ii) each neighbor u in Nul(v) is above and to the left of v, (iii) each neighbor u in Ndl(v) is below and to the left of v, (iv) each neighbor u in Ndr(v) is below and to the right of v, and (v) edges are represented by curves that are monotone with respect to each axis. By exploiting both the horizontal and the vertical relationship among vertices, windroseplanar drawings allow to simultaneously visualize two partial orders defined by means of the edges of the graph. Although the problem is NPhard in the general case, we give a polynomialtime algorithm for testing whether there exists a windroseplanar drawing that respects a combinatorial embedding that is given as part of the input. This algorithm is based on a characterization of the plane triangulations admitting a windroseplanar drawing. Furthermore, for any embedded graph admitting a windroseplanar drawing we show how to construct one with at most one bend per edge on an O(n)*O(n) grid. The latter result contrasts with the fact that straightline windroseplanar drawings may require exponential area.

Eppstein, D., Kindermann, P., Liotta, G., Lubiw, A., Maignan, A., Mondal, D., Vosoughpour, H., Whitesides, S., Wismath, S.: On the Planar Split Thickness of Graphs. In: Kranakis, E., Navarro, G., and Chávez, E. (eds.) Proceedings of the 12th Latin American Theoretical Informatics Symposium (LATIN'16). p. 403415. SpringerVerlag (2016).
Motivated by applications in graph drawing and information visualization, we examine the planar split thickness of a graph, that is, the smallest k such that the graph is ksplittable into a planar graph. A ksplit operation substitutes a vertex v by at most k new vertices such that each neighbor of v is connected to at least one of the new vertices. We first examine the planar split thickness of complete and complete bipartite graphs. We then prove that it is NPhard to recognize graphs that are 2splittable into a planar graph, and show that one can approximate the planar split thickness of a graph within a constant factor. If the treewidth is bounded, then we can even verify ksplittablity in linear time, for a constant k.

Hültenschmidt, G., Kindermann, P., Meulemans, W., Schulz, A.: Drawing Trees and Triangulations with Few Geometric Primitives. In: Barequet, G. and Papadopoulou, E. (eds.) Proceedings of the 32nd European Workshop on Computational Geometry (EuroCG'16). p. 5558. Lugano (2016).
We define the emphvisual complexity of a plane graph drawing to be the number of geometric objects needed to represent all its edges. In particular, one object may represent multiple edges (e.g. you need only one line segment to draw two collinear edges of the same vertex). We show that trees can be drawn with \($3n/4$\) straightline segments on a polynomial grid, and with \($n/2$\) straightline segments on a quasipolynomial grid. We also study the problem of drawing maximal triangulations with circular arcs and provide an algorithm to draw such graphs using only \($(5n  11)/3$\) arcs. This provides a significant improvement over the lower bound of \($2n$\) for line segments for a nontrivial graph class.

Angelini, P., Bekos, M.A., Kaufmann, M., Kindermann, P., Schneck, T.: FanBundlePlanar Drawings of Graphs. In: Hu, Y. and Nöllenburg, M. (eds.) Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD'16). p. 634636. SpringerVerlag (2016).
Fanplanar graphs seem to provide a suitable graphtheoretical foundation for edge bundling which is heavily being used for visualization purposes. We apply the fanplanarity concept to edge bundles and introduce the model of fanbundleplanarity. For the restricted onesided variant where each edge is crossed by at most one bundle and which is a special case of fanplanarity, we give a broad range of results, from recognition to edge density, from outerfanbundleplanarity to the 2layer variant. For the more natural and general twosided variant where each edge might be part of bundles with both its end segments, i.e. two bundles, we present preliminary results, observations and conjectures.

Kindermann, P., Löffler, M., Nachmanson, L., Rutter, I.: Graph Drawing Contest Report. In: Hu, Y. and Nöllenburg, M. (eds.) Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD'16). p. 589595. SpringerVerlag (2016).

Felsner, S., Igamberdiev, A., Kindermann, P., Klemz, B., Mchedlidze, T., Scheucher, M.: Strongly Monotone Drawings of Planar Graphs. In: Fekete, S. and Lubiw, A. (eds.) Proceedings of the 32nd International Symposium on Computational Geometry (SoCG'16). p. 37:137:15. Schloss Dagstuhl  LeibnizZentrum fuer Informatik (2016).
A straightline drawing of a graph is a emphmonotone drawing if for each pair of vertices there is a path which is monotonically increasing in some direction, and it is called a emphstrongly monotone drawing if the direction of monotonicity is given by the direction of the line segment connecting the two vertices. We present algorithms to compute crossingfree strongly monotone drawings for some classes of planar graphs; namely, 3connected planar graphs, outerplanar graphs, and 2trees. The drawings of 3connected planar graphs are based on primaldual circle packings. Our drawings of outerplanar graphs depend on a new algorithm that constructs strongly monotone drawings of trees which are also convex. For irreducible trees, these drawings are strictly convex.

Angelini, P., Chaplick, S., Cornelse, S., Lozzo, G.D., Battista, G.D., Eades, P., Kindermann, P., Kratochvíl, J., Lipp, F., Rutter, I.: Simultaneous Orthogonal Planarity. In: Hu, Y. and Nöllenburg, M. (eds.) Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD'16). p. 532545. SpringerVerlag (2016).
We introduce and study the OrthoSEFE\($k$\) problem: Given \($k$\) planar graphs each with maximum degree 4 and the same vertex set, is there an assignment of the vertices to grid points and of the edges to paths on the grid such that the same edges in distinct graphs are assigned the same path and such that the assignment induces a planar orthogonal drawing of each of the \($k$\) graphs? We show that the problem is NPcomplete for \($k \geq 3$\) even if the shared graph is a Hamiltonian cycle and has sunflower intersection and for \($k \geq 2$\) even if the shared graph consists of a cycle and of isolated vertices. Whereas the problem is polynomialtime solvable for \($k=2$\) when the union graph has maximum degree five and the shared graph is biconnected. Further, when the shared graph is biconnected and has sunflower intersection, we show that every positive instance has an OrthoSEFE\($k$\) with at most three bends per edge.

Felsner, S., Igamberdiev, A., Kindermann, P., Klemz, B., Mchedlidze, T., Scheucher, M.: Strongly Monotone Drawings of Planar Graphs. In: Barequet, G. and Papadopoulou, E. (eds.) Proceedings of the 32nd European Workshop on Computational Geometry (EuroCG'16). p. 5962. Lugano (2016).
A straightline drawing of a graph is a emphmonotone drawing if for each pair of vertices there is a path which is monotonically increasing in some direction, and it is called a emphstrongly monotone drawing if the direction of monotonicity is given by the direction of the line segment connecting the two vertices. We present algorithms to compute crossingfree strongly monotone drawings for some classes of planar graphs; namely, 3connected planar graphs, outerplanar graphs, and 2trees. The drawings of 3connected planar graphs are based on primaldual circle packings. Our drawings of outerplanar graphs depend on a new algorithm that constructs strongly monotone drawings of trees which are also convex. For irreducible trees, these drawings are strictly convex.

Brandenburg, F.J., Didimo, W., Evans, W.S., Kindermann, P., Liotta, G., Montecchiani, F.: Recognizing and Drawing ICPlanar Graphs. In: Di Giacomo, E. and Lubiw, A. (eds.) Proceedings of the 23rd International Symposium on Graph Drawing & Network Visualization (GD’15). p. 295308. SpringerVerlag (2015).
ICplanar graphs are those graphs that admit a drawing where no two crossed edges share an endvertex and each edge is crossed at most once. They are a proper subfamily of the 1planar graphs. Given an embedded ICplanar graph G with n vertices, we present an O(n)time algorithm that computes a straightline drawing of G in quadratic area, and an O(n^3)time algorithm that computes a straightline drawing of G with rightangle crossings in exponential area. Both these area requirements are worstcase optimal. We also show that it is NPcomplete to test ICplanarity both in the general case and in the case in which a rotation system is fixed for the input graph. Furthermore, we describe a polynomialtime algorithm to test whether a set of matching edges can be added to a triangulated planar graph such that the resulting graph is ICplanar.

Chaplick, S., Kindermann, P., Lipp, F., Wolff, A.: Solving Optimization Problems on Orthogonal Ray Graphs. Proceedings of the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG’15). p. 2 pp. (2015).
In this paper we study the class of orthogonal ray graphs (ORGs). An ORG is the intersection graph of axisparallel rays. We distinguish two subclasses of ORG, which limit the directions for the rays to two (2DORG) or three (3DORG) directions. There are several characterizations for 2DORGs and a polynomialtime recognition algorithm. We achieve some results towards a similar characterization for 3DORGs. Afterwards, we look at some wellknown combinatorial problems (e.g., MIS and FVS), which are NPhard on general graphs. We can solve these problems in polynomial times on ORGs and also give specialized algorithms for 2DORGs and 3DORGs.

Kindermann, P., Löffler, M., Nachmanson, L., Rutter, I.: Graph Drawing Contest Report. In: Giacomo, E.D. and Lubiw, A. (eds.) Proceedings of the 23rd International Symposium on Graph Drawing and Network Visualization (GD'15). p. 531537. Springer (2015).

Evans, W.S., Fleszar, K., Kindermann, P., Saeedi, N., Shin, C.S., Wolff, A.: Minimum Rectilinear Polygons for Given Angle Sequences. Proceedings of the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG’15). p. 105119. SpringerVerlag (2015).
A emphrectilinear polygon is a polygon whose edges are axisaligned. Walking counterclockwise on the boundary of such a polygon yields a sequence of left turns and right turns. The number of left turns always equals the number of right turns plus 4. It is known that any such sequence can be realized by a rectilinear polygon. In this paper, we consider the problem of finding realizations that minimize the perimeter or the area of the polygon or the area of the bounding box of the polygon. We show that all three problems are NPhard in general. Then we consider the special cases of \($x$\)monotone and \($xy$\)monotone rectilinear polygons. For these, we can optimize the three objectives efficiently.

Bereg, S., Fleszar, K., Kindermann, P., Pupyrev, S., Spoerhase, J., Wolff, A.: Colored NonCrossing Euclidean Steiner Forest. In: Elbassioni, K. and Makino, K. (eds.) Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC'15). p. 429441. SpringerVerlag (2015).
Given a set of \($k$\)colored points in the plane, we consider the problem of finding \($k$\) trees such that each tree connects all points of one color class, no two trees cross, and the total edge length of the trees is minimized. For \($k=1$\), this is the wellknown Euclidean Steiner tree problem. For general \($k$\), a \($k\rho$\)approximation algorithm is known, where \($\rho \le 1.21$\) is the Steiner ratio. We present a PTAS for \($k=2$\), a \($(5/3+\varepsilon)$\)approximation for \($k=3$\), and two approximation algorithms for general \($k$\), with ratios \($O(\sqrt n \log k)$\) and \($k+\varepsilon$\).

Bekos, M.A., van Dijk, T.C., Kindermann, P., Wolff, A.: Simultaneous Drawing of Planar Graphs with RightAngle Crossings and Few Bends. In: Rahman, M.S. and Tomita, E. (eds.) Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM'15). p. 222233. SpringerVerlag (2015).
Given two planar graphs that are defined on the same set of vertices, empha RAC simultaneous drawing is one in which each graph is drawn planar, there are no edge overlaps and the crossings between the two graphs form right angles. The geometric version restricts the problem to straightline drawings. It is known, however, that there exists a wheel and a matching which do not admit a geometric RAC simultaneous drawing. In order to enlarge the class of graphs that admit RAC simultaneous drawings, we allow bends in the resulting drawings. We prove that two planar graphs always admit a RAC simultaneous drawing with six bends per edge each, in quadratic area. For more restricted classes of planar graphs (i.e., matchings, paths, cycles, outerplanar graphs and subhamiltonian graphs), we manage to significantly reduce the required number of bends per edge, while keeping the area quadratic.

Kindermann, P., Lipp, F., Wolff, A.: Luatodonotes: Boundary Labeling for Annotations in Texts. In: Duncan, C. and Symvonis, A. (eds.) Proceedings of the 22nd International Symposium on Graph Drawing (GD'14). p. 7688. SpringerVerlag (2014).
We present a tool for annotating Latex documents with comments. Our annotations are placed in the left, right, or both margins, and connected to the corresponding positions in the text with arrows (socalled \emphleaders). Problems of this type have been studied under the name emphboundary labeling. We consider various leader types (straightline, rectilinear, and Bézier) and modify existing algorithms to allow for annotations of varying height. We have implemented our algorithms in Lua; they are available for download as an easytouse Luatex package.

Bekos, M.A., van Dijk, T.C., Fink, M., Kindermann, P., Kobourov, S., Pupyrev, S., Spoerhase, J., Wolff, A.: Improved Approximation Algorithms for Box Contact Representations. In: Schulz, A.S. and Wagner, D. (eds.) Proceedings of the 22nd European Symposium on Algorithms (ESA'14). p. 8799. SpringerVerlag (2014).
We study the following geometric representation problem: Given a graph whose vertices correspond to axisaligned rectangles with fixed dimensions, arrange the rectangles without overlaps in the plane such that two rectangles touch if the graph contains an edge between them. This problem is called textscContact Representation of Word Networks (\textscCrown) since it formalizes the geometric problem behind drawing word clouds in which semantically related words are close to each other. textscCrown is known to be NPhard, and there are approximation algorithms for certain graph classes for the optimization version, textscMaxCrown, in which realizing each desired adjacency yields a certain profit. We present the first \($O(1)$\)approximation algorithm for the general case, when the input is a complete weighted graph, and for the bipartite case. Since the subgraph of realized adjacencies is necessarily planar, we also consider several planar graph classes (namely stars, trees, outerplanar, and planar graphs), improving upon the known results. For some graph classes, we also describe improvements in the unweighted case, where each adjacency yields the same profit. Finally, we show that the problem is APXhard on bipartite graphs of bounded maximum degree.

Kindermann, P., Schulz, A., Spoerhase, J., Wolff, A.: On Monotone Drawings of Trees. In: Duncan, C. and Symvonis, A. (eds.) Proceedings of the 22nd International Symposium on Graph Drawing (GD'14). p. 488500. SpringerVerlag (2014).
A crossingfree straightline drawing of a graph is emphmonotone if there is a monotone path between any pair of vertices with respect to emphsome direction. We show how to construct a monotone drawing of a tree with \($n$\) vertices on an \($O(n^1.5) times O(n^1.5)$\) grid whose angles are close to the best possible angular resolution. Our drawings are emphconvex, that is, if every edge to a leaf is substituted by a ray, the (unbounded) faces form convex regions. It is known that convex drawings are monotone and, in the case of trees, also crossingfree. A monotone drawing is emphstrongly monotone if, for every pair of vertices, the direction that witnesses the monotonicity comes from the vector that connects the two vertices. We show that every tree admits a strongly monotone drawing. For biconnected outerplanar graphs, this is easy to see. On the other hand, we present a simplyconnected graph that does not have a strongly monotone drawing in any embedding.

Alam, M.J., Bekos, M.A., Kaufmann, M., Kindermann, P., Kobourov, S.G., Wolff, A.: Smooth Orthogonal Drawings of Planar Graphs. In: Pardo, A. and Viola, A. (eds.) Proc. 11th Latin American Sympos. on Theoretical Informatics (LATIN'14). p. 144155. SpringerVerlag (2014).
In emphsmooth orthogonal layouts of planar graphs, every edge is an alternating sequence of axisaligned segments and circular arcs with common axisaligned tangents. In this paper, we study the problem of finding smooth orthogonal layouts of low emphedge complexity, that is, with few segments per edge. We say that a graph has emphsmooth complexity \($k$\)for short, an SC_klayoutif it admits a smooth orthogonal drawing of edge complexity at most~\($k$\). Our main result is that every 4planar graph has an SC_2layout. While our drawings may have superpolynomial area, we show that, for 3planar graphs, cubic area suffices. Further, we show that every biconnected 4outerplane graph admits an SC_1layout. On the negative side, we demonstrate a family of biconnected 4planar graphs that requires exponential area for an SC_1layout. Finally, we present an infinite family of biconnected 4planar graphs that does not admit an SC_1layout.

Bekos, M.A., van Dijk, T.C., Kindermann, P., Wolff, A.: Simultaneous Drawing of Planar Graphs with RightAngle Crossings and Few Bends. In: Duncan, C. and Symvonis, A. (eds.) Proceedings of the 22nd International Symposium on Graph Drawing (GD'14). p. 515516. SpringerVerlag (2014).
Given two planar graphs that are defined on the same set of vertices, empha RAC simultaneous drawing is one in which each graph is drawn planar, there are no edge overlaps and the crossings between the two graphs form right angles. The geometric version restricts the problem to straightline drawings. It is known, however, that there exists a wheel and a matching which do not admit a geometric RAC simultaneous drawing. In order to enlarge the class of graphs that admit RAC simultaneous drawings, we allow bends in the resulting drawings. We prove that two planar graphs always admit a RAC simultaneous drawing with six bends per edge each, in quadratic area. For more restricted classes of planar graphs (i.e., matchings, paths, cycles, outerplanar graphs and subhamiltonian graphs), we manage to significantly reduce the required number of bends per edge, while keeping the area quadratic.

Kindermann, P., Niedermann, B., Rutter, I., Schaefer, M., Schulz, A., Wolff, A.: TwoSided Boundary Labeling with Adjacent Sides. In: Dehne, F., SolisOba, R., and Sack, J.R. (eds.) Proceedings of the 13th International Algorithms and Data Structure Symposium (WADS'13). p. 463474. SpringerVerlag (2013).
In the emphBoundary Labeling problem, we are given a set of \($n$\) points, referred to as emphsites, inside an axisparallel rectangle \($R$\), and a set of \($n$\) pairwise disjoint rectangular labels that are attached to \($R$\) from the outside. The task is to connect the sites to the labels by nonintersecting rectilinear paths, socalled emphleaders, with at most one bend. In this paper, we study the problem emphTwoSided Boundary Labeling with Adjacent Sides, where labels lie on two adjacent sides of the enclosing rectangle. We present a polynomialtime algorithm that computes a crossingfree leader layout if one exists. So far, such an algorithm has only been known for the cases that labels lie on one side or on two opposite sides of \($R$\) (where a crossingfree solution always exists). For the more difficult case where labels lie on adjacent sides, we show how to compute crossingfree leader layouts that maximize the number of labeled points or minimize the total leader length.

Kindermann, P., Niedermann, B., Rutter, I., Schaefer, M., Schulz, A., Wolff, A.: TwoSided Boundary Labeling with Adjacent Sides. In: Fekete, S. (ed.) Proceedings of the 29th European Workshop on Computational Geometry (EuroCG'13). p. 233236. , Braunschweig (2013).
In the emphBoundary Labeling problem, we are given a set of~\($n$\) points, referred to as emphsites, inside an axisparallel rectangle~\($R$\), and a set of~\($n$\) pairwise disjoint rectangular labels that are attached to~\($R$\) from the outside. The task is to connect the sites to the labels by nonintersecting polygonal paths, socalled emphleaders. In this paper, we study the emphTwoSided Boundary Labeling with Adjacent Sides problem, with labels lying on two adjacent sides of the enclosing rectangle. We restrict ourselves to rectilinear leaders with at most one bend. We present a polynomialtime algorithm that computes a crossingfree leader layout if one exists. So far, such an algorithm has only been known for the simpler cases that labels lie on one side or on two opposite sides of~\($R$\) (where a crossingfree solution always exists).
PhD or Master Thesis
[
to top
]