
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., 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.

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.

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). 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). 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., 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.

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., 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.

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.

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.

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). pp. 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.

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).

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.

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.

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.

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.

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.

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 (2016).
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.

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.

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. 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., 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).

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.

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.

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.

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.

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.

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.

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.

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.

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).

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$\).

Kindermann, P.: Angular Schematization in Graph Drawing, https://opus.bibliothek.uniwuerzburg.de/frontdoor/index/index/docId/11254, (2015).
Graphs are a frequently used tool to model relationships among entities. A graph is a binary relation between objects, that is, it consists of a set of objects (vertices) and a set of pairs of objects (edges). Networks are common examples of modeling data as a graph. For example, relationships between persons in a social network, or network links between computers in a telecommunication network can be represented by a graph. The clearest way to illustrate the modeled data is to visualize the graphs. The field of Graph Drawing deals with the problem of finding algorithms to automatically generate graph visualizations. The task is to find a "good" drawing, which can be measured by different criteria such as number of crossings between edges or the used area. In this thesis, we study Angular Schematization in Graph Drawing. By this, we mean drawings with large angles (for example, between the edges at common vertices or at crossing points). The thesis consists of three parts. First, we deal with the placement of boxes. Boxes are axisparallel rectangles that can, for example, contain text. They can be placed on a map to label important sites, or can be used to describe semantic relationships between words in a word network. In the second part of the thesis, we consider graph drawings visually guide the viewer. These drawings generally induce large angles between edges that meet at a vertex. Furthermore, the edges are drawn crossingfree and in a way that makes them easy to follow for the human eye. The third and final part is devoted to crossings with large angles. In drawings with crossings, it is important to have large angles between edges at their crossing point, preferably right angles.

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.

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.

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., 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., 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.