-
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, 977--994 (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 NP-hard to recognize graphs that are 2-splittable 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 Direction-Constrained Edges. Transactions on Algorithms. 14, 54:1--54: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 emphwindrose-planar 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, windrose-planar drawings allow to simultaneously visualize two partial orders defined by means of the edges of the graph. Although the problem is NP-hard in the general case, we give a polynomial-time algorithm for testing whether there exists a windrose-planar 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 windrose-planar drawing. Furthermore, for any embedded graph admitting a windrose-planar 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 straight-line windrose-planar 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, 312--327 (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 NP-hard. 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 Bar-Visibility Graphs. In: Durocher, S. and Kamali, S. (eds.) Proceedings of the 30th Canadian Conference on Computational Geometry (CCCG'18). p. 230--246. University of Manitoba (2018).
In this paper, we take another look at unit bar-visibility representations, that is bar-visibility representations where every bar has the same width. Motivated by some applications in textile construction, we restrict the graphs further to integral unit bar-visibility representations (IUBVR), that is a bar-visibility representation where the bar of every vertex is a horizontal line segment [i-1,i], for some positive integer i, at some real-value 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 NP-hard to test whether a graph has an IUBVR. We also present recursive algorithms to create IUBVRs for some graph classes, such as 2-connected outerplanar graphs with maximum degree 4. In the strong model, we provide a polynomial-time 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). Springer-Verlag (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 linear-time 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 polynomial-time testing and drawing algorithm for a meaningful subset of instances.
-
Kindermann, P., Montecchiani, F., Schlipf, L., Schulz, A.: Drawing Subcubic 1-Planar 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). Springer-Verlag (2018).
We show that the 1-planar slope number of 3-connected cubic 1-planar 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 1-bend edges. We also show that two slopes always suffice for 1-planar drawings of subcubic 1-planar graphs with at most two bends per edge. This bound is obtained with vertex and crossing resolution pi/2. For straight-line drawings of 1-plane graphs, we present lower bounds for the 1-planar 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, 501--518 (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 furthest-pair or shortest-path task on the drawings.
-
Angelini, P., Bekos, M.A., Kaufmann, M., Kindermann, P., Schneck, T.: 1-Fan-Bundle-Planar Drawings of Graphs. Theoretical Computer Science. 723, 23--50 (2018).
Edge bundling is an important concept heavily used for graph visualization purposes. To enable the comparison with other established nearly-planarity models in graph drawing, we formulate a new edge-bundling model which is inspired by the recently introduced fan-planar graphs. In particular, we restrict the bundling to the endsegments of the edges. As in 1-planarity, we call our model emph1-fan-bundle-planarity, 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 2-layer 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:1--53:6. FU Berlin (2018).
Given a set of colored points in the plane, we ask if there exists a crossing-free straight-line drawing of a spanning forest, such that every tree in the forest contains exactly the points of one color class. We show that the problem is NP-complete, 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 NP-complete 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, 357--387 (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$\) straight-line segments on a polynomial grid, and with \($n/2$\) straight-line segments on a quasi-polynomial 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. 52--64. Springer-Verlag (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 furthest-pair or shortest-path 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 Graph-Theoretic Concepts in Computer Science (WG'17). pp. 316-329. Springer-Verlag (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$\) straight-line segments on a polynomial grid, and with \($n/2$\) straight-line segments on a quasi-polynomial 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. 575--582. Springer-Verlag (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. 113--126. Springer (2017).
Knot and link diagrams are projections of one or more 3-dimensional 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 4-regular 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 circular-arc 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 4-regular plane multigraphs that do have Lombardi drawings. We then study two relaxations of Lombardi drawings and show that every knot admits a plane 2-Lombardi drawing (where edges are composed of two circular arcs). Further, every knot is near-Lombardi, 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.: 1-Fan-Bundle-Planar 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. 517--530. Springer-Verlag (2017).
Edge bundling is an important concept heavily used for graph visualization purposes. To enable the comparison with other established nearly-planarity models in graph drawing, we formulate a new edge-bundling model which is inspired by the recently introduced fan-planar graphs. In particular, we restrict the bundling to the endsegments of the edges. As in 1-planarity, we call our model 1-fan-bundle-planarity, 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 2-layer 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:1--4:12. Schloss Dagstuhl - Leibniz-Zentrum 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 NP-hard. 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.: Multi-Sided Boundary Labeling. Algorithmica. 76, 225--258 (2016).
In the Boundary Labeling problem, we are given a set of \($n$\) points, referred to as sites, inside an axis-parallel 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 non-intersecting rectilinear paths, so-called leaders, with at most one bend. In this paper, we study the Multi-Sided Boundary Labeling problem, with labels lying on at least two sides of the enclosing rectangle. We present a polynomial-time algorithm that computes a crossing-free 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 crossing-free 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 crossing-free leader layout that labels all sites and also for maximizing the number of labeled sites in a crossing-free leader layout. For two-sided boundary labeling with adjacent sides, we further show how to minimize the total leader length in a crossing-free 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, 133--158 (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 straight-line 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, 902--920 (2016).
We study the following geometric representation problem: Given a graph whose vertices correspond to axis-aligned 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 NP-hard, and there are approximation algorithms for certain graph classes for the optimization version, textscMax-Crown, 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 APX-hard 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 Direction-Constrained Edges. In: Krauthgamer, R. (ed.) Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'16). p. 985--996. 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 windrose-planar 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, windrose-planar drawings allow to simultaneously visualize two partial orders defined by means of the edges of the graph. Although the problem is NP-hard in the general case, we give a polynomial-time algorithm for testing whether there exists a windrose-planar 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 windrose-planar drawing. Furthermore, for any embedded graph admitting a windrose-planar 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 straight-line windrose-planar 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. 403--415. Springer-Verlag (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 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 NP-hard to recognize graphs that are 2-splittable 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.
-
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. 59--62. Lugano (2016).
A straight-line 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 crossing-free strongly monotone drawings for some classes of planar graphs; namely, 3-connected planar graphs, outerplanar graphs, and 2-trees. The drawings of 3-connected planar graphs are based on primal-dual 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 IC-Planar Graphs. Theoretical Computer Science. 636, 1--16 (2016).
IC-planar graphs are those graphs that admit a drawing where no two crossed edges share an end-vertex and each edge is crossed at most once. They are a proper subfamily of the 1-planar graphs. Given an embedded IC-planar graph \($G$\) with \($n$\) vertices, we present an \($O(n)$\)-time algorithm that computes a straight-line drawing of \($G$\) in quadratic area, and an \($O(n^3)$\)-time algorithm that computes a straight-line drawing of \($G$\) with right-angle crossings in exponential area. Both these area requirements are worst-case optimal. We also show that it is NP-complete to test IC-planarity both in the general case and in the case in which a rotation system is fixed for the input graph. Furthermore, we describe a polynomial-time algorithm to test whether a set of matching edges can be added to a triangulated planar graph such that the resulting graph is IC-planar.
-
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. 589--595. Springer-Verlag (2016).
-
Angelini, P., Bekos, M.A., Kaufmann, M., Kindermann, P., Schneck, T.: Fan-Bundle-Planar 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. 634--636. Springer-Verlag (2016).
Fan-planar graphs seem to provide a suitable graph-theoretical foundation for edge bundling which is heavily being used for visualization purposes. We apply the fan-planarity concept to edge bundles and introduce the model of fan-bundle-planarity. For the restricted one-sided variant where each edge is crossed by at most one bundle and which is a special case of fan-planarity, we give a broad range of results, from recognition to edge density, from outer-fan-bundle-planarity to the 2-layer variant. For the more natural and general two-sided 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. 532--545. Springer-Verlag (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 NP-complete 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 polynomial-time 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. 55--58. 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$\) straight-line segments on a polynomial grid, and with \($n/2$\) straight-line segments on a quasi-polynomial 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:1--37:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016).
A straight-line 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 crossing-free strongly monotone drawings for some classes of planar graphs; namely, 3-connected planar graphs, outerplanar graphs, and 2-trees. The drawings of 3-connected planar graphs are based on primal-dual 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 Right-Angle 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. 222--233. Springer-Verlag (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 straight-line 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. 105--119. Springer-Verlag (2015).
A emphrectilinear polygon is a polygon whose edges are axis-aligned. 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 NP-hard 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 axis-parallel 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 polynomial-time recognition algorithm. We achieve some results towards a similar characterization for 3DORGs. Afterwards, we look at some well-known combinatorial problems (e.g., MIS and FVS), which are NP-hard 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 IC-Planar Graphs. In: Di Giacomo, E. and Lubiw, A. (eds.) Proceedings of the 23rd International Symposium on Graph Drawing & Network Visualization (GD’15). p. 295--308. Springer-Verlag (2015).
IC-planar graphs are those graphs that admit a drawing where no two crossed edges share an end-vertex and each edge is crossed at most once. They are a proper subfamily of the 1-planar graphs. Given an embedded IC-planar graph G with n vertices, we present an O(n)-time algorithm that computes a straight-line drawing of G in quadratic area, and an O(n^3)-time algorithm that computes a straight-line drawing of G with right-angle crossings in exponential area. Both these area requirements are worst-case optimal. We also show that it is NP-complete to test IC-planarity both in the general case and in the case in which a rotation system is fixed for the input graph. Furthermore, we describe a polynomial-time algorithm to test whether a set of matching edges can be added to a triangulated planar graph such that the resulting graph is IC-planar.
-
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. 531--537. Springer (2015).
-
Bereg, S., Fleszar, K., Kindermann, P., Pupyrev, S., Spoerhase, J., Wolff, A.: Colored Non-Crossing Euclidean Steiner Forest. In: Elbassioni, K. and Makino, K. (eds.) Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC'15). p. 429--441. Springer-Verlag (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 well-known 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.uni-wuerzburg.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 axis-parallel 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 crossing-free 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. 144--155. Springer-Verlag (2014).
In emphsmooth orthogonal layouts of planar graphs, every edge is an alternating sequence of axis-aligned segments and circular arcs with common axis-aligned 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_k-layout---if it admits a smooth orthogonal drawing of edge complexity at most~\($k$\). Our main result is that every 4-planar graph has an SC_2-layout. While our drawings may have super-polynomial area, we show that, for 3-planar graphs, cubic area suffices. Further, we show that every biconnected 4-outerplane graph admits an SC_1-layout. On the negative side, we demonstrate a family of biconnected 4-planar graphs that requires exponential area for an SC_1-layout. Finally, we present an infinite family of biconnected 4-planar graphs that does not admit an SC_1-layout.
-
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. 488--500. Springer-Verlag (2014).
A crossing-free straight-line 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 crossing-free. 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 simply-connected 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. 87--99. Springer-Verlag (2014).
We study the following geometric representation problem: Given a graph whose vertices correspond to axis-aligned 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 NP-hard, and there are approximation algorithms for certain graph classes for the optimization version, textscMax-Crown, 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 APX-hard 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. 76--88. Springer-Verlag (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 (so-called \emphleaders). Problems of this type have been studied under the name emphboundary labeling. We consider various leader types (straight-line, 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 easy-to-use Luatex package.
-
Bekos, M.A., van Dijk, T.C., Kindermann, P., Wolff, A.: Simultaneous Drawing of Planar Graphs with Right-Angle Crossings and Few Bends. In: Duncan, C. and Symvonis, A. (eds.) Proceedings of the 22nd International Symposium on Graph Drawing (GD'14). p. 515--516. Springer-Verlag (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 straight-line 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.
orcid.org/0000-0001-5764-7719
