
Angelini, P., Chaplick, S., Cornelse, S., Lozzo, G.D., Battista, G.D., Eades, P., Kindermann, P., Kratochv\'\il, J., Lipp, F., Rutter, I.: Simultaneous Orthogonal Planarity. In: Hu, Y. and Nöllenburg, M. (eds.) Proc. 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.

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

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

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., Niedermann, B., Rutter, I., Schaefer, M., Schulz, A., Wolff, A.: MultiSided Boundary Labeling. Algorithmica. 76, 225258 (2016).
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 \emphMultiSided 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 that labels lie on one side or on two opposite sides of~$R$ (where 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 labeld 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.

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.

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. (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., Bekos, M.A., Kaufmann, M., Kindermann, P., Schneck, T.: FanBundlePlanar Drawings of Graphs. In: Hu, Y. and Nöllenburg, M. (eds.) Proc. 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., 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.

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.

Bereg, S., Fleszar, K., Kindermann, P., Pupyrev, S., Spoerhase, J., Wolff, A.: Colored NonCrossing Euclidean Steiner Forest. In: Elbassioni, K. and Makino, K. (eds.) Proceecings of the 26th International Symposium on Algorithms and Computation (ISAAC 2015). 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$.

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

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

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.

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.

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