Prof. Dr. Philipp Kindermann

• [ Article ]
• [ Inproceedings ]
• [ Mastersthesis ]
• [ PhD thesis ]

• Drawing Subcubic 1-Planar Graphs with Few Bends, Few Slopes, and Large Angles. Kindermann, Philipp; Montecchiani, Fabrizio; Schlipf, Lena; Schulz, André. In Journal of Graph Algorithms and Applications, 25(1), pp. 1–28. 2020.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  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.

  @article{kmss-ds1pg-jgaa20, abstract = {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.}, author = {Kindermann, Philipp and Montecchiani, Fabrizio and Schlipf, Lena and Schulz, André}, journal = {Journal of Graph Algorithms and Applications}, keywords = {myown}, number = 1, pages = {1–28}, title = {Drawing Subcubic 1-Planar Graphs with Few Bends, Few Slopes, and Large Angles}, volume = 25, year = 2020 }
• Recognizing Stick Graphs with and without Length Constraints. Chaplick, Steven; Kindermann, Philipp; L{{ö}}ffler, Andre; Thiele, Florian; Wolff, Alexander; Zaft, Alexander; Zink, Johannes. In Journal of Graph Algorithms and Applications, 24(4), pp. 657–681. 2020.
  • [ BibTeX ]
  • [ DOI ]
  @article{ckltwzz-rsglc-jgaa20, author = {Chaplick, Steven and Kindermann, Philipp and L{\"{o}}ffler, Andre and Thiele, Florian and Wolff, Alexander and Zaft, Alexander and Zink, Johannes}, journal = {Journal of Graph Algorithms and Applications}, keywords = {myown}, note = {Special Issue on Selected Papers from GD 2020}, number = 4, pages = {657–681}, title = {Recognizing Stick Graphs with and without Length Constraints}, volume = 24, year = 2020 }
• Lombardi Drawings of Knots and Links. Kindermann, Philipp; Kobourov, Stephen; L{ö}ffler, Maarten; N{ö}llenburg, Martin; Schulz, Andr{é}; Vogtenhuber, Birgit. In Journal of Computational Geometry, 10(1), pp. 444–476. 2019.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  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 \emph{near-Lombardi}, that is, it can be drawn as Lombardi drawing when relaxing the angular resolution requirement by an arbitrary small angular offset $\eps$, while maintaining a $180^\circ$ angle between opposite edges.

  @article{kklnsv-ldkl-jocg19, abstract = {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 \emph{near-Lombardi}, that is, it can be drawn as Lombardi drawing when relaxing the angular resolution requirement by an arbitrary small angular offset $\eps$, while maintaining a $180^\circ$ angle between opposite edges.}, author = {Kindermann, Philipp and Kobourov, Stephen and L{\"o}ffler, Maarten and N{\"o}llenburg, Martin and Schulz, Andr{\'e} and Vogtenhuber, Birgit}, journal = {Journal of Computational Geometry}, keywords = {myown}, number = 1, pages = {444–476}, title = {Lombardi Drawings of Knots and Links}, volume = 10, year = 2019 }
• Greedy Rectilinear Drawings. Angelini, Patrizio; Bekos, Michael; Didimo, Walter; Grilli, Luca; Kindermann, Philipp; Mchedlidze, Tamara; Prutkin, Roman; Symvonis, Antonios; Tappini, Alessandra. In Theoretical Computer Science, 795, pp. 375–397. 2019.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  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.

  @article{abdgkmpst-grd-gd18, abstract = {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.}, author = {Angelini, Patrizio and Bekos, Michael and Didimo, Walter and Grilli, Luca and Kindermann, Philipp and Mchedlidze, Tamara and Prutkin, Roman and Symvonis, Antonios and Tappini, Alessandra}, journal = {Theoretical Computer Science}, keywords = {myown}, pages = {375–397}, title = {Greedy Rectilinear Drawings}, volume = 795, year = 2019 }
• Windrose Planarity: Embedding Graphs with Direction-Constrained Edges. Angelini, Patrizio; Lozzo, Giordano Da; Battista, Giuseppe Di; Donato, Valentino Di; Kindermann, Philipp; Rote, G{{ü}}nter; Rutter, Ignaz. In Transactions on Algorithms, 14(4), pp. 54:1–54:24. 2018.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  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 \emph{windrose-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.

  @article{adddkrr-wpegd-talg18, abstract = {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 \emph{windrose-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.}, author = {Angelini, Patrizio and Lozzo, Giordano Da and Battista, Giuseppe Di and Donato, Valentino Di and Kindermann, Philipp and Rote, G{\"{u}}nter and Rutter, Ignaz}, journal = {Transactions on Algorithms}, keywords = {myown}, month = {09}, number = 4, pages = {54:1–54:24}, title = {Windrose Planarity: Embedding Graphs with Direction-Constrained Edges}, volume = 14, year = 2018 }
• 1-Fan-Bundle-Planar Drawings of Graphs. Angelini, Patrizio; Bekos, Michael A.; Kaufmann, Michael; Kindermann, Philipp; Schneck, Thomas. In Theoretical Computer Science, 723, pp. 23–50. 2018.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  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 \emph{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.

  @article{abkks-1fbpd-tcs18, abstract = {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 \emph{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.}, author = {Angelini, Patrizio and Bekos, Michael A. and Kaufmann, Michael and Kindermann, Philipp and Schneck, Thomas}, journal = {Theoretical Computer Science}, keywords = {myown}, month = {05}, pages = {23–50}, title = {1-Fan-Bundle-Planar Drawings of Graphs}, volume = 723, year = 2018 }
• On the Planar Split Thickness of Graphs. Eppstein, David; Kindermann, Philipp; Kobourov, Stephen; Liotta, Giuseppe; Lubiw, Anna; Maignan, Aude; Mondal, Debajyoti; Vosoughpour, Hamideh; Whitesides, Sue; Wismath, Stephen. In Algorithmica, 80(3), pp. 977–994. 2018.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  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$.

  @article{ekkllmmvww-opstg-A17, abstract = {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$.}, author = {Eppstein, David and Kindermann, Philipp and Kobourov, Stephen and Liotta, Giuseppe and Lubiw, Anna and Maignan, Aude and Mondal, Debajyoti and Vosoughpour, Hamideh and Whitesides, Sue and Wismath, Stephen}, journal = {Algorithmica}, keywords = {thickness}, month = {03}, note = {Special Issue on Selected Papers from LATIN 2016}, number = 3, pages = {977–994}, title = {On the Planar Split Thickness of Graphs}, volume = 80, year = 2018 }
• Experimental analysis of the accessibility of drawings with few segments. Kindermann, Philipp; Meulemans, Wouter; Schulz, Andr{é}. In Journal of Graph Algorithms and Applications, 22(3), pp. 501–518. 2018.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  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.

  @article{kms-eaadf-jgaa18, abstract = {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.}, author = {Kindermann, Philipp and Meulemans, Wouter and Schulz, Andr{\'e}}, journal = {Journal of Graph Algorithms and Applications}, keywords = {myown}, note = {Special Issue on Selected Papers from GD 2017.}, number = 3, pages = {501–518}, series = {Lecture Notes in Computer Science}, title = {Experimental analysis of the accessibility of drawings with few segments}, volume = 22, year = 2018 }
• Drawing Planar Graphs with Few Geometric Primitives. H{ü}ltenschmidt, Gregor; Kindermann, Philipp; Meulemans, Wouter; Schulz, Andr{é}. In Journal of Graph Algorithms and Applications, 22(2), pp. 357–387. 2018.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  We define the \emph{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.

  @article{hkms-dttfg-jgaa18, abstract = {We define the \emph{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.}, author = {H{\"u}ltenschmidt, Gregor and Kindermann, Philipp and Meulemans, Wouter and Schulz, Andr{\'e}}, journal = {Journal of Graph Algorithms and Applications}, keywords = {myown}, number = 2, pages = {357–387}, title = {Drawing Planar Graphs with Few Geometric Primitives}, volume = 22, year = 2018 }
• Placing your Coins on a Shelf. Alt, Helmut; Buchin, Kevin; Chaplick, Steven; Cheong, Otfried; Kindermann, Philipp; Knauer, Christian; Stehn, Fabian. In Journal of Computational Geometry, 9(1), pp. 312–327. 2018.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  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.

  @article{abcckks-pycos-jocg18, abstract = {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.}, author = {Alt, Helmut and Buchin, Kevin and Chaplick, Steven and Cheong, Otfried and Kindermann, Philipp and Knauer, Christian and Stehn, Fabian}, journal = {Journal of Computational Geometry}, keywords = {myown}, number = 1, pages = {312–327}, title = {Placing your Coins on a Shelf}, volume = 9, year = 2018 }
• Improved Approximation Algorithms for Box Contact Representations. Bekos, Michael A.; van Dijk, Thomas C.; Fink, Martin; Kindermann, Philipp; Kobourov, Stephen; Pupyrev, Sergey; Spoerhase, Joachim; Wolff, Alexander. In Algorithmica, 77(3), pp. 902–920. 2017.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  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 \textsc{Contact Representation of Word Networks} (\textsc{Crown}) since it formalizes the geometric problem behind drawing word clouds in which semantically related words are close to each other. \textsc{Crown} is known to be NP-hard, and there are approximation algorithms for certain graph classes for the optimization version, \textsc{Max-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.

  @article{bdfkkpsw-iaabcr-a16, abstract = {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 \textsc{Contact Representation of Word Networks} (\textsc{Crown}) since it formalizes the geometric problem behind drawing word clouds in which semantically related words are close to each other. \textsc{Crown} is known to be NP-hard, and there are approximation algorithms for certain graph classes for the optimization version, \textsc{Max-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.}, author = {Bekos, Michael A. and van Dijk, Thomas C. and Fink, Martin and Kindermann, Philipp and Kobourov, Stephen and Pupyrev, Sergey and Spoerhase, Joachim and Wolff, Alexander}, journal = {Algorithmica}, keywords = {word}, month = {03}, number = 3, pages = {902–920}, title = {Improved Approximation Algorithms for Box Contact Representations}, volume = 77, year = 2017 }
• Multi-Sided Boundary Labeling. Kindermann, Philipp; Niedermann, Benjamin; Rutter, Ignaz; Schaefer, Marcus; Schulz, Andr{é}; Wolff, Alexander. In Algorithmica, 76(1), pp. 225–258. 2016.
  • [ Abstract ]
  • [ BibTeX ]
  • [ URL ]
  • [ arxiv ]
  • [ slides ]
  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.

  @article{knrssw-tsblas-A16, abstract = {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.}, author = {Kindermann, Philipp and Niedermann, Benjamin and Rutter, Ignaz and Schaefer, Marcus and Schulz, Andr{\'e} and Wolff, Alexander}, journal = {Algorithmica}, keywords = {myown}, month = {08}, number = 1, pages = {225–258}, title = {Multi-Sided Boundary Labeling}, volume = 76, year = 2016 }
• Recognizing and Drawing IC-Planar Graphs. Brandenburg, Franz J.; Didimo, Walter; Evans, William S.; Kindermann, Philipp; Liotta, Giuseppe; Montecchiani, Fabrizio. In Theoretical Computer Science, 636, pp. 1–16. 2016.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  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.

  @article{bdeklm-rdicp-tcs16, abstract = {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.}, author = {Brandenburg, Franz J. and Didimo, Walter and Evans, William S. and Kindermann, Philipp and Liotta, Giuseppe and Montecchiani, Fabrizio}, journal = {Theoretical Computer Science}, keywords = {rac}, month = {06}, pages = {1–16}, title = {Recognizing and Drawing IC-Planar Graphs}, volume = 636, year = 2016 }
• Simultaneous Drawing of Planar Graphs with Right–Angle Crossings and Few Bends. Bekos, Michael A.; van Dijk, Thomas C.; Kindermann, Philipp; Wolff, Alexander. In Journal of Graph Algorithms and Applications, 20(1), pp. 133–158. 2016.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  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.

  @article{bdkw-sdpgr-JGAA16, abstract = {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.}, author = {Bekos, Michael A. and van Dijk, Thomas C. and Kindermann, Philipp and Wolff, Alexander}, journal = {Journal of Graph Algorithms and Applications}, keywords = {drawing}, month = {02}, note = {Special Issue on Selected Papers from WALCOM 2015}, number = 1, pages = {133–158}, title = {Simultaneous Drawing of Planar Graphs with Right–Angle Crossings and Few Bends}, volume = 20, year = 2016 }

• Extending Partial Representations of Rectangular Duals with Given Contact Orientations. Chaplick, Steven; Kindermann, Philipp; Klawitter, Jonathan; Rutter, Ignaz; Wolff, Alexander. In Proceedings of the 12th International Conference on Algorithms and Complexity (CIAC’21), A. Philippou, C. Georgiou (eds.). 2021.
  • [ Abstract ]
  • [ BibTeX ]
  A rectangular dual of a graph G is a contact representation of G with axis-aligned rectangles such that (i) no four rectangles share a point and (ii) the union of all rectangles is a rectangle. The partial representation extension problem for rectangular duals asks whether a given partial rectangular dual can be extended to a rectangular dual, that is, whether there exists a rectangular dual where some vertices are represented by prescribed rectangles. Combinatorially, a rectangular dual can be described by a regular edge labeling (REL), which determines the orientations of the rectangle contacts. We characterize the RELs that admit an extension, which leads to a linear-time testing algorithm. In the affirmative, we can construct an extension in linear time.

  @inproceedings{ckkrw-eprrd-ciac21, abstract = {A rectangular dual of a graph G is a contact representation of G with axis-aligned rectangles such that (i) no four rectangles share a point and (ii) the union of all rectangles is a rectangle. The partial representation extension problem for rectangular duals asks whether a given partial rectangular dual can be extended to a rectangular dual, that is, whether there exists a rectangular dual where some vertices are represented by prescribed rectangles. Combinatorially, a rectangular dual can be described by a regular edge labeling (REL), which determines the orientations of the rectangle contacts. We characterize the RELs that admit an extension, which leads to a linear-time testing algorithm. In the affirmative, we can construct an extension in linear time.}, author = {Chaplick, Steven and Kindermann, Philipp and Klawitter, Jonathan and Rutter, Ignaz and Wolff, Alexander}, booktitle = {Proceedings of the 12th International Conference on Algorithms and Complexity (CIAC'21)}, editor = {Philippou, Anna and Georgiou, Chryssis}, keywords = {myown}, note = {To appear}, title = {Extending Partial Representations of Rectangular Duals with Given Contact Orientations}, year = 2021 }
• The Complexity of Finding Tangles. Firman, Oksana; Felsner, Stefan; Kindermann, Philipp; Ravsky, Alexander; Wolff, Alexander; Zink, Johannes. In Proceedings of the 36th European Workshop on Computational Geometry (EuroCG’20), S. Chaplick, P. Kindermann, A. Wolff (eds.), pp. 67:1–67:8. Würzburg, 2020.
  • [ Abstract ]
  • [ BibTeX ]
  • [ URL ]
  We study the following combinatorial problem. Given a set of n y-monotone curves, which we call wires, a tangle determines the order of the wires on a number of horizontal layers such that the orders of the wires on any two consecutive layers differ only in swaps of neighboring wires. Given a multiset L of swaps (that is, unordered pairs of wires) and an initial order of the wires, a tangle realizes L if each pair of wires changes its order exactly as many times as specified by L. Finding a tangle that realizes a given multiset of swaps and uses the least number of layers is known to be NP-hard. We show that it is even NP-hard to decide if a realizing tangle exists.

  @inproceedings{ffkrwz-tcft-eurocg20, abstract = {We study the following combinatorial problem. Given a set of n y-monotone curves, which we call wires, a tangle determines the order of the wires on a number of horizontal layers such that the orders of the wires on any two consecutive layers differ only in swaps of neighboring wires. Given a multiset L of swaps (that is, unordered pairs of wires) and an initial order of the wires, a tangle realizes L if each pair of wires changes its order exactly as many times as specified by L. Finding a tangle that realizes a given multiset of swaps and uses the least number of layers is known to be NP-hard. We show that it is even NP-hard to decide if a realizing tangle exists.}, author = {Firman, Oksana and Felsner, Stefan and Kindermann, Philipp and Ravsky, Alexander and Wolff, Alexander and Zink, Johannes}, booktitle = {Proceedings of the 36th European Workshop on Computational Geometry (EuroCG'20)}, editor = {Chaplick, Steven and Kindermann, Philipp and Wolff, Alexander}, keywords = {myown}, note = {Abstract}, pages = {67:1–67:8}, publisher = {Würzburg}, title = {The Complexity of Finding Tangles}, year = 2020 }
• Graph Drawing Contest Report. Kindermann, Philipp; Mchedlidze, Tamara; Meulemans, Wouter; Rutter, Ignaz. In Proc. 28th International Symposium on Graph Drawing and Network Visualization (GD’20), D. Auber, P. Valtr (eds.). 2020.
  • [ BibTeX ]
  • [ URL ]
  • [ slides ]
  • [ video ]
  @inproceedings{kmmr-gdcr-gd20, author = {Kindermann, Philipp and Mchedlidze, Tamara and Meulemans, Wouter and Rutter, Ignaz}, booktitle = {Proc. 28th International Symposium on Graph Drawing and Network Visualization (GD'20)}, editor = {Auber, David and Valtr, Pavel}, keywords = {graph}, note = {To appear}, title = {Graph Drawing Contest Report}, year = 2020 }
• The Complexity of Finding Tangles. Firman, Oksana; Felsner, Stefan; Kindermann, Philipp; Ravsky, Alexander; Wolff, Alexander; Zink, Johannes. In Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD’20), D. Auber, P. Valtr (eds.). 2020.
  • [ Abstract ]
  • [ BibTeX ]
  We study the following combinatorial problem. Given a set of n y-monotone curves, which we call wires, a tangle determines the order of the wires on a number of horizontal layers such that the orders of the wires on any two consecutive layers differ only in swaps of neighboring wires. Given a multiset L of swaps (that is, unordered pairs of wires) and an initial order of the wires, a tangle realizes L if each pair of wires changes its order exactly as many times as specified by L. Finding a tangle that realizes a given multiset of swaps and uses the least number of layers is known to be NP-hard. We show that it is even NP-hard to decide if a realizing tangle exists.

  @inproceedings{ffkrwz-tcft-gd20poster, abstract = {We study the following combinatorial problem. Given a set of n y-monotone curves, which we call wires, a tangle determines the order of the wires on a number of horizontal layers such that the orders of the wires on any two consecutive layers differ only in swaps of neighboring wires. Given a multiset L of swaps (that is, unordered pairs of wires) and an initial order of the wires, a tangle realizes L if each pair of wires changes its order exactly as many times as specified by L. Finding a tangle that realizes a given multiset of swaps and uses the least number of layers is known to be NP-hard. We show that it is even NP-hard to decide if a realizing tangle exists.}, author = {Firman, Oksana and Felsner, Stefan and Kindermann, Philipp and Ravsky, Alexander and Wolff, Alexander and Zink, Johannes}, booktitle = {Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD'20)}, editor = {Auber, David and Valtr, Pavel}, keywords = {myown}, note = {Poster. To appear}, title = {The Complexity of Finding Tangles}, year = 2020 }
• One-Bend Drawings of Outerplanar Graphs Inside Simple Polygons. Angelini, Patrizio; Kindermann, Philipp; Löffler, Andre; Schlipf, Lena; Symvonis, Antonios. In Proceedings of the 36th European Workshop on Computational Geometry (EuroCG’20), S. Chaplick, P. Kindermann, A. Wolff (eds.), pp. 70:1–70:6. Würzburg, 2020.
  • [ Abstract ]
  • [ BibTeX ]
  • [ URL ]
  We consider the problem of drawing an outerplanar graph with n vertices with at most one bend per edge if the outer face is already drawn as a simple polygon with m corners. We prove that it can be decided in O(mn) time if such a drawing exists. In the positive case, our algorithm also outputs such a drawing.

  @inproceedings{aklss-obdog-eurocg20, abstract = {We consider the problem of drawing an outerplanar graph with n vertices with at most one bend per edge if the outer face is already drawn as a simple polygon with m corners. We prove that it can be decided in O(mn) time if such a drawing exists. In the positive case, our algorithm also outputs such a drawing.}, author = {Angelini, Patrizio and Kindermann, Philipp and Löffler, Andre and Schlipf, Lena and Symvonis, Antonios}, booktitle = {Proceedings of the 36th European Workshop on Computational Geometry (EuroCG'20)}, editor = {Chaplick, Steven and Kindermann, Philipp and Wolff, Alexander}, keywords = {myown}, note = {Abstract}, pages = {70:1–70:6}, publisher = {Würzburg}, title = {One-Bend Drawings of Outerplanar Graphs Inside Simple Polygons}, year = 2020 }
• On Mixed Linear Layouts of Series-Parallel Graphs. Angelini, Patrizio; Bekos, Michael; Kindermann, Philipp; Mchedlidze, Tamara. In Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD’20), D. Auber, P. Valtr (eds.). 2020.
  • [ Abstract ]
  • [ BibTeX ]
  A mixed s-stack q-queue layout of a graph consists of a linear ordering of its vertices and of a partition of its edges into s stacks and q queues, such that no two edges in the same stack cross and no two edges in the same queue nest. In 1992, Heath and Rosenberg conjectured that every planar graph admits a mixed 1-stack 1-queue layout. Recently, Pupyrev disproved this conjectured by demonstrating a planar partial 3-tree that does not admit a 1-stack 1-queue layout. In this note, we strengthen Pupyrev's result by showing that the conjecture does not hold even for 2-trees.

  @inproceedings{abkm-mllsp-gd20, abstract = {A mixed s-stack q-queue layout of a graph consists of a linear ordering of its vertices and of a partition of its edges into s stacks and q queues, such that no two edges in the same stack cross and no two edges in the same queue nest. In 1992, Heath and Rosenberg conjectured that every planar graph admits a mixed 1-stack 1-queue layout. Recently, Pupyrev disproved this conjectured by demonstrating a planar partial 3-tree that does not admit a 1-stack 1-queue layout. In this note, we strengthen Pupyrev's result by showing that the conjecture does not hold even for 2-trees.}, author = {Angelini, Patrizio and Bekos, Michael and Kindermann, Philipp and Mchedlidze, Tamara}, booktitle = {Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD'20)}, editor = {Auber, David and Valtr, Pavel}, keywords = {myown}, note = {To appear}, title = {On Mixed Linear Layouts of Series-Parallel Graphs}, year = 2020 }
• Computing Height-Optimal Tangles Faster. Firman, Oksana; Kindermann, Philipp; Ravsky, Alexander; Wolff, Alexander; Zink, Johannes. In Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD’19), Vol. 11904 of Lecture Notes in Computer Science, D. Archambault, C. D. T{ó}th (eds.), pp. 203–215. Springer-Verlag, 2019.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  We study the following combinatorial problem. Given a set of n y-monotone wires, a tangle determines the order of the wires on a number of horizontal layers such that the orders of the wires on any two consecutive layers differ only in swaps of neighboring wires. Given a multiset L of swaps (that is, unordered pairs of numbers between 1 and n) and an initial order of the wires, a tangle realizes L if each pair of wires changes its order exactly as many times as specified by L. The aim is to find a tangle that realizes L using the smallest number of layers. We show that this problem is NP-hard, and we give an algorithm that computes an optimal tangle for n wires and a given list L of swaps in O((2|L|/n^2+1)^(n^2/2)phi^n n) time, where phi~1.618 is the golden ratio. We can treat lists where every swap occurs at most once in O(n! phi^n) time. We implemented the algorithm for the general case and compared it to an existing algorithm.

  @inproceedings{fkrwz-cotf-gd19, abstract = {We study the following combinatorial problem. Given a set of n y-monotone wires, a tangle determines the order of the wires on a number of horizontal layers such that the orders of the wires on any two consecutive layers differ only in swaps of neighboring wires. Given a multiset L of swaps (that is, unordered pairs of numbers between 1 and n) and an initial order of the wires, a tangle realizes L if each pair of wires changes its order exactly as many times as specified by L. The aim is to find a tangle that realizes L using the smallest number of layers. We show that this problem is NP-hard, and we give an algorithm that computes an optimal tangle for n wires and a given list L of swaps in O((2|L|/n^2+1)^(n^2/2)phi^n n) time, where phi 1.618 is the golden ratio. We can treat lists where every swap occurs at most once in O(n! phi^n) time. We implemented the algorithm for the general case and compared it to an existing algorithm.}, author = {Firman, Oksana and Kindermann, Philipp and Ravsky, Alexander and Wolff, Alexander and Zink, Johannes}, booktitle = {Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD'19)}, editor = {Archambault, Daniel and T\'{o}th, Csaba D.}, keywords = {myown}, pages = {203–215}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Computing Height-Optimal Tangles Faster}, volume = 11904, year = 2019 }
• Finding Tutte Paths in Linear Time. Biedl, Therese; Kindermann, Philipp. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP’19), Vol. 132 of LIPIcs, C. Baier, I. Chatzigiannakis, P. Flocchini, S. Leonardi (eds.), pp. 23:1–23:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  It is well-known that every planar graph has a Tutte path, i.e., a path P such that any component of G-P has at most three attachment points on P. However, it was only recently shown that such Tutte paths can be found in polynomial time. In this paper, we give a new proof that 3-connected planar graphs have Tutte paths, which leads to a linear-time algorithm to find Tutte paths. Furthermore, our Tutte path has special properties: it visits all exterior vertices, all components of G-P have exactly three attachment points, and we can assign distinct representatives to them that are interior vertices. Finally, our running time bound is slightly stronger; we can bound it in terms of the degrees of the faces that are incident to P. This allows us to find some applications of Tutte paths (such as binary spanning trees and 2-walks) in linear time as well.

  @inproceedings{bk-ftplt-icalp19, abstract = {It is well-known that every planar graph has a Tutte path, i.e., a path P such that any component of G-P has at most three attachment points on P. However, it was only recently shown that such Tutte paths can be found in polynomial time. In this paper, we give a new proof that 3-connected planar graphs have Tutte paths, which leads to a linear-time algorithm to find Tutte paths. Furthermore, our Tutte path has special properties: it visits all exterior vertices, all components of G-P have exactly three attachment points, and we can assign distinct representatives to them that are interior vertices. Finally, our running time bound is slightly stronger; we can bound it in terms of the degrees of the faces that are incident to P. This allows us to find some applications of Tutte paths (such as binary spanning trees and 2-walks) in linear time as well.}, author = {Biedl, Therese and Kindermann, Philipp}, booktitle = {Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP'19)}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, keywords = {myown}, pages = {23:1–23:14}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, series = {LIPIcs}, title = {Finding Tutte Paths in Linear Time}, volume = 132, year = 2019 }
• Maximum Matchings and Minimum Blocking Sets in $\Theta_6$-Graphs. Biedl, Therese; Biniaz, Ahmad; Irvine, Veronika; Jain, Kshitij; Kindermann, Philipp; Lubiw, Anna. In Proceedings of the 35th European Workshop on Computational Geometry (EuroCG’19), M. Löffler (ed.). Utrecht, 2019.
  • [ Abstract ]
  • [ BibTeX ]
  • [ URL ]
  • [ arxiv ]
  • [ slides ]
  Theta_6-graphs are important geometric graphs that have many applications. They are equivalent to Delaunay graphs where empty equilateral triangles with a horizontal edge take the place of empty circles. We investigate lower bounds on the size of maximum matchings in these graphs. The best known lower bound is (n-1)/3, where n is the number of vertices of the graph. Babu et al. (2014) conjectured that any Theta_6-graph has a perfect matching (as is true for standard Delaunay graphs). Although this conjecture remains open, we improve the lower bound to (3n-8)/7. We also relate the size of maximum matchings in Theta_6-graphs to the minimum size of a blocking set. Every edge of a Theta_6-graph on a point set P corresponds to an empty triangle that contains the endpoints of the edge but no other point of P. A blocking set has at least one point in each such triangle. We prove that the size of a maximum matching is at least b(n)/2 where b(n) is the minimum, over all Theta_6-graphs with n vertices, of the minimum size of a blocking set. In the other direction, lower bounds on matchings allow us to show that b(n) >= 3n/4 - 2.

  @inproceedings{bbijkl-mmmbs-eurocg19, abstract = {Theta_6-graphs are important geometric graphs that have many applications. They are equivalent to Delaunay graphs where empty equilateral triangles with a horizontal edge take the place of empty circles. We investigate lower bounds on the size of maximum matchings in these graphs. The best known lower bound is (n-1)/3, where n is the number of vertices of the graph. Babu et al. (2014) conjectured that any Theta_6-graph has a perfect matching (as is true for standard Delaunay graphs). Although this conjecture remains open, we improve the lower bound to (3n-8)/7. We also relate the size of maximum matchings in Theta_6-graphs to the minimum size of a blocking set. Every edge of a Theta_6-graph on a point set P corresponds to an empty triangle that contains the endpoints of the edge but no other point of P. A blocking set has at least one point in each such triangle. We prove that the size of a maximum matching is at least b(n)/2 where b(n) is the minimum, over all Theta_6-graphs with n vertices, of the minimum size of a blocking set. In the other direction, lower bounds on matchings allow us to show that b(n) >= 3n/4 - 2.}, author = {Biedl, Therese and Biniaz, Ahmad and Irvine, Veronika and Jain, Kshitij and Kindermann, Philipp and Lubiw, Anna}, booktitle = {Proceedings of the 35th European Workshop on Computational Geometry (EuroCG'19)}, editor = {Löffler, Maarten}, keywords = {myown}, note = {Abstract}, publisher = {Utrecht}, title = {Maximum Matchings and Minimum Blocking Sets in $\Theta_6$-Graphs}, year = 2019 }
• Drawing Planar Graphs with Few Segments on a Polynomial Grid. Kindermann, Philipp; Mchedlidze, Tamara; Schneck, Thomas; Symvonis, Antonios. In Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD’19), Vol. 11904 of Lecture Notes in Computer Science, D. Archambault, C. D. T{ó}th (eds.), pp. 416–429. Springer-Verlag, 2019.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  The visual complexity of a graph drawing can be measured by the number of geometric objects used for the representation of its elements. In this paper, we study planar graph drawings where edges are represented by few segments. In such a drawing, one segment may represent multiple edges forming a path. Drawings of planar graphs with few segments were intensively studied in the past years. However, the area requirements were only considered for limited subclasses of planar graphs. In this paper, we show that trees have drawings with 3n/4-1 segments and n^2 area, improving the previous result of O(n^{3.58}). We also show that 3-connected planar graphs and biconnected outerplanar graphs have a drawing with 8n/3-O(1) and 3n/2-O(1) segments, respectively, and O(n^3) area.

  @inproceedings{kmss-dpgfs-gd19, abstract = {The visual complexity of a graph drawing can be measured by the number of geometric objects used for the representation of its elements. In this paper, we study planar graph drawings where edges are represented by few segments. In such a drawing, one segment may represent multiple edges forming a path. Drawings of planar graphs with few segments were intensively studied in the past years. However, the area requirements were only considered for limited subclasses of planar graphs. In this paper, we show that trees have drawings with 3n/4-1 segments and n^2 area, improving the previous result of O(n^{3.58}). We also show that 3-connected planar graphs and biconnected outerplanar graphs have a drawing with 8n/3-O(1) and 3n/2-O(1) segments, respectively, and O(n^3) area.}, author = {Kindermann, Philipp and Mchedlidze, Tamara and Schneck, Thomas and Symvonis, Antonios}, booktitle = {Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD'19)}, editor = {Archambault, Daniel and T\'{o}th, Csaba D.}, keywords = {myown}, pages = {416–429}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Drawing Planar Graphs with Few Segments on a Polynomial Grid}, volume = 11904, year = 2019 }
• Crossing Numbers of Beyond-Planar Graphs. Chimani, Markus; Kindermann, Philipp; Montecchiani, Fabrizio; Valtr, Pavel. In Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD’19), Vol. 11904 of Lecture Notes in Computer Science, D. Archambault, C. D. T{ó}th (eds.), pp. 78–86. Springer-Verlag, 2019.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  We study lower bounds on the minimum number of crossings for 1-planar, quasi-planar, and fan-planar graphs. We prove that there are n-vertex 1-planar (quasi-planar, fan-planar) graphs such that any 1-planar (quasi-planar, fan-planar) drawing has Omega(n) crossings, while O(1) crossings suffice in a crossing-minimal drawing with no restrictions on local edge crossing patterns.

  @inproceedings{ckmv-cnbpg-gd19, abstract = {We study lower bounds on the minimum number of crossings for 1-planar, quasi-planar, and fan-planar graphs. We prove that there are n-vertex 1-planar (quasi-planar, fan-planar) graphs such that any 1-planar (quasi-planar, fan-planar) drawing has Omega(n) crossings, while O(1) crossings suffice in a crossing-minimal drawing with no restrictions on local edge crossing patterns.}, author = {Chimani, Markus and Kindermann, Philipp and Montecchiani, Fabrizio and Valtr, Pavel}, booktitle = {Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD'19)}, editor = {Archambault, Daniel and T\'{o}th, Csaba D.}, keywords = {myown}, pages = {78–86}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Crossing Numbers of Beyond-Planar Graphs}, volume = 11904, year = 2019 }
• Stick Graphs with Length Constraints. Chaplick, Steven; Kindermann, Philipp; L{ö}ffler, Andre; Thiele, Florian; Wolff, Alexander; Zaft, Alexander; Zink, Johannes. In Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD’19), Vol. 11904 of Lecture Notes in Computer Science, D. Archambault, C. D. T{ó}th (eds.), pp. 3–17. Springer-Verlag, 2019.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  Stick graphs are intersection graphs of horizontal and vertical line segments that all touch a line of slope -1 and lie above this line. De Luca et al. [GD’18] considered the recognition problem of stick graphs when no order is given (STICK), when the order of either one of the two sets is given (STICK_A), and when the order of both sets is given (STICK_AB). They showed how to solve STICK_AB efficiently. In this paper, we improve the running time of their algorithm, and we solve STICK_A efficiently. Further, we consider variants of these problems where the lengths of the sticks are given as input. We show that these variants of STICK, STICK_A , and STICK_AB are all NP-complete. On the positive side, we give an efficient solution for STICK_AB with fixed stick lengths if there are no isolated vertices.

  @inproceedings{ckltwzz-sglc-gd19, abstract = {Stick graphs are intersection graphs of horizontal and vertical line segments that all touch a line of slope -1 and lie above this line. De Luca et al. [GD’18] considered the recognition problem of stick graphs when no order is given (STICK), when the order of either one of the two sets is given (STICK_A), and when the order of both sets is given (STICK_AB). They showed how to solve STICK_AB efficiently. In this paper, we improve the running time of their algorithm, and we solve STICK_A efficiently. Further, we consider variants of these problems where the lengths of the sticks are given as input. We show that these variants of STICK, STICK_A , and STICK_AB are all NP-complete. On the positive side, we give an efficient solution for STICK_AB with fixed stick lengths if there are no isolated vertices.}, author = {Chaplick, Steven and Kindermann, Philipp and L\"{o}ffler, Andre and Thiele, Florian and Wolff, Alexander and Zaft, Alexander and Zink, Johannes}, booktitle = {Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD'19)}, editor = {Archambault, Daniel and T\'{o}th, Csaba D.}, keywords = {myown}, pages = {3–17}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Stick Graphs with Length Constraints}, volume = 11904, year = 2019 }
• Graph Drawing Contest Report. Kindermann, Philipp; Mchedlidze, Tamara; Rutter, Ignaz. In Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD’19), Vol. 11904 of Lecture Notes in Computer Science, D. Archambault, C. D. T{ó}th (eds.), pp. 575–583. Springer-Verlag, 2019.
  • [ BibTeX ]
  • [ URL ]
  • [ DOI ]
  • [ slides ]
  @inproceedings{kmr-gdcr-gd19, author = {Kindermann, Philipp and Mchedlidze, Tamara and Rutter, Ignaz}, booktitle = {Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD'19)}, editor = {Archambault, Daniel and T\'{o}th, Csaba D.}, keywords = {myown}, pages = {575–583}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Graph Drawing Contest Report}, volume = 11904, year = 2019 }
• Computing Optimal Tangles Faster. Firman, Oksana; Kindermann, Philipp; Ravsky, Alexander; Wolff, Alexander; Zink, Johannes. In Proceedings of the 12th Annual Meeting of the Asian Association for Algorithms and Computation (AAAC’19), S.-W. Cheng (ed.). Seoul, 2019.
  • [ Abstract ]
  • [ BibTeX ]
  • [ arxiv ]
  • [ slides ]
  We study the following combinatorial problem. Given a set of n y-monotone wires, a tangle determines the order of the wires on a number of horizontal layers such that the orders of the wires on any two consecutive layers differ only in swaps of neighboring wires. Given a multiset L of swaps (that is, unordered pairs of numbers between 1 and n) and an initial order of the wires, a tangle realizes L if each pair of wires changes its order exactly as many times as specified by L. The aim is to find a tangle that realizes L using the smallest number of layers. We show that this problem is NP-hard, and we give an algorithm that computes an optimal tangle for n wires and a given list L of swaps in O((2|L|/n^2+1)^(n^2/2)phi^n n) time, where phi~1.618 is the golden ratio. We can treat lists where every swap occurs at most once in O(n! phi^n) time. We implemented the algorithm for the general case and compared it to an existing algorithm.

  @inproceedings{fkrwz-cotf-aaac19, abstract = {We study the following combinatorial problem. Given a set of n y-monotone wires, a tangle determines the order of the wires on a number of horizontal layers such that the orders of the wires on any two consecutive layers differ only in swaps of neighboring wires. Given a multiset L of swaps (that is, unordered pairs of numbers between 1 and n) and an initial order of the wires, a tangle realizes L if each pair of wires changes its order exactly as many times as specified by L. The aim is to find a tangle that realizes L using the smallest number of layers. We show that this problem is NP-hard, and we give an algorithm that computes an optimal tangle for n wires and a given list L of swaps in O((2|L|/n^2+1)^(n^2/2)phi^n n) time, where phi 1.618 is the golden ratio. We can treat lists where every swap occurs at most once in O(n! phi^n) time. We implemented the algorithm for the general case and compared it to an existing algorithm.}, author = {Firman, Oksana and Kindermann, Philipp and Ravsky, Alexander and Wolff, Alexander and Zink, Johannes}, booktitle = {Proceedings of the 12th Annual Meeting of the Asian Association for Algorithms and Computation (AAAC'19)}, editor = {Cheng, Siu-Wing}, keywords = {myown}, note = {Abstract}, publisher = {Seoul}, title = {Computing Optimal Tangles Faster}, year = 2019 }
• Computing Optimal Tangles Faster. Firman, Oksana; Kindermann, Philipp; Ravsky, Alexander; Wolff, Alexander; Zink, Johannes. In Proceedings of the 35th European Workshop on Computational Geometry (EuroCG’19), M. Löffler (ed.). Utrecht, 2019.
  • [ Abstract ]
  • [ BibTeX ]
  • [ URL ]
  • [ arxiv ]
  • [ slides ]
  We study the following combinatorial problem. Given a set of n y-monotone wires, a tangle determines the order of the wires on a number of horizontal layers such that the orders of the wires on any two consecutive layers differ only in swaps of neighboring wires. Given a multiset L of swaps (that is, unordered pairs of numbers between 1 and n) and an initial order of the wires, a tangle realizes L if each pair of wires changes its order exactly as many times as specified by L. The aim is to find a tangle that realizes L using the smallest number of layers. We show that this problem is NP-hard, and we give an algorithm that computes an optimal tangle for n wires and a given list L of swaps in O((2|L|/n^2+1)^(n^2/2)phi^n n) time, where phi~1.618 is the golden ratio. We can treat lists where every swap occurs at most once in O(n! phi^n) time. We implemented the algorithm for the general case and compared it to an existing algorithm.

  @inproceedings{fkrwz-cotf-eurocg19, abstract = {We study the following combinatorial problem. Given a set of n y-monotone wires, a tangle determines the order of the wires on a number of horizontal layers such that the orders of the wires on any two consecutive layers differ only in swaps of neighboring wires. Given a multiset L of swaps (that is, unordered pairs of numbers between 1 and n) and an initial order of the wires, a tangle realizes L if each pair of wires changes its order exactly as many times as specified by L. The aim is to find a tangle that realizes L using the smallest number of layers. We show that this problem is NP-hard, and we give an algorithm that computes an optimal tangle for n wires and a given list L of swaps in O((2|L|/n^2+1)^(n^2/2)phi^n n) time, where phi 1.618 is the golden ratio. We can treat lists where every swap occurs at most once in O(n! phi^n) time. We implemented the algorithm for the general case and compared it to an existing algorithm.}, author = {Firman, Oksana and Kindermann, Philipp and Ravsky, Alexander and Wolff, Alexander and Zink, Johannes}, booktitle = {Proceedings of the 35th European Workshop on Computational Geometry (EuroCG'19)}, editor = {Löffler, Maarten}, keywords = {myown}, note = {Abstract}, publisher = {Utrecht}, title = {Computing Optimal Tangles Faster}, year = 2019 }
• Maximum Matchings and Minimum Blocking Sets in $\Theta_6$-Graphs. Biedl, Therese; Biniaz, Ahmad; Irvine, Veronika; Jain, Kshitij; Kindermann, Philipp; Lubiw, Anna. In Proceedings of the 45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG’19), Vol. 11789 of Lecture Notes in Computer Science, I. Sau, D. M. Thilikos (eds.), pp. 258–270. Springer-Verlag, 2019.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  Theta_6-graphs are important geometric graphs that have many applications. They are equivalent to Delaunay graphs where empty equilateral triangles with a horizontal edge take the place of empty circles. We investigate lower bounds on the size of maximum matchings in these graphs. The best known lower bound is (n-1)/3, where n is the number of vertices of the graph. Babu et al. (2014) conjectured that any Theta_6-graph has a perfect matching (as is true for standard Delaunay graphs). Although this conjecture remains open, we improve the lower bound to (3n-8)/7. We also relate the size of maximum matchings in Theta_6-graphs to the minimum size of a blocking set. Every edge of a Theta_6-graph on a point set P corresponds to an empty triangle that contains the endpoints of the edge but no other point of P. A blocking set has at least one point in each such triangle. We prove that the size of a maximum matching is at least b(n)/2 where b(n) is the minimum, over all Theta_6-graphs with n vertices, of the minimum size of a blocking set. In the other direction, lower bounds on matchings allow us to show that b(n) >= 3n/4 - 2.

  @inproceedings{bbijkl-mmmbs-wg19, abstract = {Theta_6-graphs are important geometric graphs that have many applications. They are equivalent to Delaunay graphs where empty equilateral triangles with a horizontal edge take the place of empty circles. We investigate lower bounds on the size of maximum matchings in these graphs. The best known lower bound is (n-1)/3, where n is the number of vertices of the graph. Babu et al. (2014) conjectured that any Theta_6-graph has a perfect matching (as is true for standard Delaunay graphs). Although this conjecture remains open, we improve the lower bound to (3n-8)/7. We also relate the size of maximum matchings in Theta_6-graphs to the minimum size of a blocking set. Every edge of a Theta_6-graph on a point set P corresponds to an empty triangle that contains the endpoints of the edge but no other point of P. A blocking set has at least one point in each such triangle. We prove that the size of a maximum matching is at least b(n)/2 where b(n) is the minimum, over all Theta_6-graphs with n vertices, of the minimum size of a blocking set. In the other direction, lower bounds on matchings allow us to show that b(n) >= 3n/4 - 2.}, author = {Biedl, Therese and Biniaz, Ahmad and Irvine, Veronika and Jain, Kshitij and Kindermann, Philipp and Lubiw, Anna}, booktitle = {Proceedings of the 45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'19)}, editor = {Sau, Ignasi and Thilikos, Dimitrios M.}, keywords = {myown}, pages = {258–270}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Maximum Matchings and Minimum Blocking Sets in $\Theta_6$-Graphs}, volume = 11789, year = 2019 }
• Graph Drawing Contest Report. Devanny, William; Kindermann, Philipp; L{{ö}}ffler, Maarten; Rutter, Ignaz. In Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD’18), Vol. 11282 of Lecture Notes in Computer Science, T. Biedl, A. Kerren (eds.), pp. 609–617. Springer-Verlag, 2018.
  • [ BibTeX ]
  • [ URL ]
  • [ DOI ]
  • [ slides ]
  @inproceedings{dklr-gdcr-gd18, author = {Devanny, William and Kindermann, Philipp and L{\"{o}}ffler, Maarten and Rutter, Ignaz}, booktitle = {Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD'18)}, editor = {Biedl, Therese and Kerren, Andreas}, keywords = {myown}, month = {09}, pages = {609–617}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Graph Drawing Contest Report}, volume = 11282, year = 2018 }
• Greedy Rectilinear Drawings. Angelini, Patrizio; Bekos, Michael; Didimo, Walter; Grilli, Luca; Kindermann, Philipp; Mchedlidze, Tamara; Prutkin, Roman; Symvonis, Antonios; Tappini, Alessandra. In Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD’18), Vol. 11282 of Lecture Notes in Computer Science, T. Biedl, A. Kerren (eds.), pp. 495–508. Springer-Verlag, 2018.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  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.

  @inproceedings{abdgkmpst-grd-gd18, abstract = {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.}, author = {Angelini, Patrizio and Bekos, Michael and Didimo, Walter and Grilli, Luca and Kindermann, Philipp and Mchedlidze, Tamara and Prutkin, Roman and Symvonis, Antonios and Tappini, Alessandra}, booktitle = {Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD'18)}, editor = {Biedl, Therese and Kerren, Andreas}, keywords = {myown}, month = {09}, pages = {495–508}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Greedy Rectilinear Drawings}, volume = 11282, year = 2018 }
• Drawing Subcubic 1-Planar Graphs with Few Bends, Few Slopes, and Large Angles. Kindermann, Philipp; Montecchiani, Fabrizio; Schlipf, Lena; Schulz, André. In Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD’18), Vol. 11282 of Lecture Notes in Computer Science, T. Biedl, A. Kerren (eds.), pp. 152–166. Springer-Verlag, 2018.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  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.

  @inproceedings{kmss-ds1pg-gd18, abstract = {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.}, author = {Kindermann, Philipp and Montecchiani, Fabrizio and Schlipf, Lena and Schulz, André}, booktitle = {Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD'18)}, editor = {Biedl, Therese and Kerren, Andreas}, keywords = {myown}, month = {09}, pages = {152–166}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Drawing Subcubic 1-Planar Graphs with Few Bends, Few Slopes, and Large Angles}, volume = 11282, year = 2018 }
• Integral Unit Bar-Visibility Graphs. Biedl, Therese; Biniaz, Ahmad; Irvine, Veronika; Kindermann, Philipp; Naredla, Anurag Murty; Turcotte, Alexi. In Proceedings of the 30th Canadian Conference on Computational Geometry (CCCG’18), S. Durocher, S. Kamali (eds.), pp. 230–246. University of Manitoba, 2018.
  • [ Abstract ]
  • [ BibTeX ]
  • [ URL ]
  • [ slides ]
  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.

  @inproceedings{bbiknt-iubvg-cccg18, abstract = {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.}, author = {Biedl, Therese and Biniaz, Ahmad and Irvine, Veronika and Kindermann, Philipp and Naredla, Anurag Murty and Turcotte, Alexi}, booktitle = {Proceedings of the 30th Canadian Conference on Computational Geometry (CCCG'18)}, editor = {Durocher, Stephane and Kamali, Shahin}, keywords = {myown}, month = {08}, pages = {230–246}, publisher = {University of Manitoba}, title = {Integral Unit Bar-Visibility Graphs}, year = 2018 }
• The Partition Spanning Forest Problem. Kindermann, Philipp; Klemz, Boris; Rutter, Ignaz; Schnider, Patrick; Schulz, Andr{é}. In Proceedings of the 34th European Workshop on Computational Geometry (EuroCG’18), W. Mulzer (ed.), pp. 53:1–53:6. FU Berlin, 2018.
  • [ Abstract ]
  • [ BibTeX ]
  • [ URL ]
  • [ arxiv ]
  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.

  @inproceedings{kkrss-tpsfp-eurocg18, abstract = {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.}, author = {Kindermann, Philipp and Klemz, Boris and Rutter, Ignaz and Schnider, Patrick and Schulz, Andr{\'e}}, booktitle = {Proceedings of the 34th European Workshop on Computational Geometry (EuroCG'18)}, editor = {Mulzer, Wolfgang}, keywords = {myown}, month = {03}, pages = {53:1–53:6}, publisher = {FU Berlin}, title = {The Partition Spanning Forest Problem}, year = 2018 }
• Drawing Planar Graphs with Few Geometric Primitives. H{ü}ltenschmidt, Gregor; Kindermann, Philipp; Meulemans, Wouter; Schulz, Andr{é}. In Proceedings of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG’17), Vol. 10520 of Lecture Notes in Computer Science, H. L. Bodlaender, G. J. Woeginger (eds.), pp. 316–329. Springer-Verlag, 2017.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  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.

  @inproceedings{hkms-dttfg-wg17, abstract = {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.}, author = {H{\"u}ltenschmidt, Gregor and Kindermann, Philipp and Meulemans, Wouter and Schulz, Andr{\'e}}, booktitle = {Proceedings of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'17)}, editor = {Bodlaender, Hans L. and Woeginger, Gerhard J.}, keywords = {visual}, month = {06}, pages = {316–329}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Drawing Planar Graphs with Few Geometric Primitives}, volume = 10520, year = 2017 }
• Graph Drawing Contest Report. Devanny, William; Kindermann, Philipp; L{{ö}}ffler, Maarten; Rutter, Ignaz. In Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD’17), Vol. 10692 of Lecture Notes in Computer Science, F. Frati, K.-L. Ma (eds.), pp. 575–582. Springer-Verlag, 2017.
  • [ BibTeX ]
  • [ URL ]
  • [ DOI ]
  • [ slides ]
  @inproceedings{dklr-gdcr-gd17, author = {Devanny, William and Kindermann, Philipp and L{\"{o}}ffler, Maarten and Rutter, Ignaz}, booktitle = {Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD'17)}, editor = {Frati, Fabrizio and Ma, Kwan-Liu}, keywords = {contest}, month = {09}, pages = {575–582}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Graph Drawing Contest Report}, volume = 10692, year = 2017 }
• Experimental analysis of the accessibility of drawings with few segments. Kindermann, Philipp; Meulemans, Wouter; Schulz, Andr{é}. In Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD’17), Vol. 10692 of Lecture Notes in Computer Science, F. Frati, K.-L. Ma (eds.), pp. 52–64. Springer-Verlag, 2017.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  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.

  @inproceedings{kms-eaadf-gd17, abstract = {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.}, author = {Kindermann, Philipp and Meulemans, Wouter and Schulz, Andr{\'e}}, booktitle = {Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD'17)}, editor = {Frati, Fabrizio and Ma, Kwan-Liu}, keywords = {myown}, month = {09}, pages = {52–64}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Experimental analysis of the accessibility of drawings with few segments}, volume = 10692, year = 2017 }
• 1-Fan-Bundle-Planar Drawings of Graphs. Angelini, Patrizio; Bekos, Michael A.; Kaufmann, Michael; Kindermann, Philipp; Schneck, Thomas. In Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD’17), Vol. 10692 of Lecture Notes in Computer Science, F. Frati, K.-L. Ma (eds.), pp. 517–530. Springer-Verlag, 2017.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  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.

  @inproceedings{abkks-1fbpd-gd17, abstract = {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.}, author = {Angelini, Patrizio and Bekos, Michael A. and Kaufmann, Michael and Kindermann, Philipp and Schneck, Thomas}, booktitle = {Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD'17)}, editor = {Frati, Fabrizio and Ma, Kwan-Liu}, keywords = {myown}, month = {09}, pages = {517–530}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {1-Fan-Bundle-Planar Drawings of Graphs}, volume = 10692, year = 2017 }
• Placing your Coins on a Shelf. Alt, Helmut; Buchin, Kevin; Chaplick, Steven; Cheong, Otfried; Kindermann, Philipp; Knauer, Christian; Stehn, Fabian. In Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC’17), Vol. 92, Y. Okamoto, T. Tokuyama (eds.), pp. 4:1–4:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.
  • [ Abstract ]
  • [ BibTeX ]
  • [ URL ]
  • [ DOI ]
  • [ arxiv ]
  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.

  @inproceedings{kklnsv-ldkl-gd17, abstract = {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.}, author = {Alt, Helmut and Buchin, Kevin and Chaplick, Steven and Cheong, Otfried and Kindermann, Philipp and Knauer, Christian and Stehn, Fabian}, booktitle = {Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC'17)}, editor = {Okamoto, Yoshio and Tokuyama, Takeshi}, keywords = {packing}, month = 12, pages = {4:1–4:12}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, title = {Placing your Coins on a Shelf}, volume = 92, year = 2017 }
• Lombardi Drawings of Knots and Links. Kindermann, Philipp; Kobourov, Stephen; L{ö}ffler, Maarten; N{ö}llenburg, Martin; Schulz, Andr{é}; Vogtenhuber, Birgit. In Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD’17), Vol. 10692 of Lecture Notes in Computer Science, F. Frati, K.-L. Ma (eds.), pp. 113–126. Springer, 2017.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  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.

  @inproceedings{kklnsv-ldkl-gd17, abstract = {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.}, author = {Kindermann, Philipp and Kobourov, Stephen and L{\"o}ffler, Maarten and N{\"o}llenburg, Martin and Schulz, Andr{\'e} and Vogtenhuber, Birgit}, booktitle = {Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD'17)}, editor = {Frati, Fabrizio and Ma, Kwan-Liu}, keywords = {myown}, month = {09}, pages = {113–126}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Lombardi Drawings of Knots and Links}, volume = 10692, year = 2017 }
• Simultaneous Orthogonal Planarity. Angelini, Patrizio; Chaplick, Steven; Cornelse, Sabine; Lozzo, Giordano Da; Battista, Giuseppe Di; Eades, Peter; Kindermann, Philipp; Kratochv{í}l, Jan; Lipp, Fabian; Rutter, Ignaz. In Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD’16), Vol. 9801 of Lecture Notes in Computer Science, Y. Hu, M. N{ö}llenburg (eds.), pp. 532–545. Springer-Verlag, 2016.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  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.

  @inproceedings{accddekklr-sop-gd16, abstract = {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.}, author = {Angelini, Patrizio and Chaplick, Steven and Cornelse, Sabine and Lozzo, Giordano Da and Battista, Giuseppe Di and Eades, Peter and Kindermann, Philipp and Kratochv{\'i}l, Jan and Lipp, Fabian and Rutter, Ignaz}, booktitle = {Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD'16)}, editor = {Hu, Yifan and N{\"o}llenburg, Martin}, keywords = {simultaneous}, month = {09}, pages = {532–545}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Simultaneous Orthogonal Planarity}, volume = 9801, year = 2016 }
• Graph Drawing Contest Report. Kindermann, Philipp; L{{ö}}ffler, Maarten; Nachmanson, Lev; Rutter, Ignaz. In Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD’16), Vol. 9801 of Lecture Notes in Computer Science, Y. Hu, M. N{ö}llenburg (eds.), pp. 589–595. Springer-Verlag, 2016.
  • [ BibTeX ]
  • [ URL ]
  • [ DOI ]
  • [ slides ]
  @inproceedings{klnr-gdcr-gd16, author = {Kindermann, Philipp and L{\"{o}}ffler, Maarten and Nachmanson, Lev and Rutter, Ignaz}, booktitle = {Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD'16)}, editor = {Hu, Yifan and N{\"o}llenburg, Martin}, keywords = {myown}, month = {09}, pages = {589–595}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Graph Drawing Contest Report}, volume = 9801, year = 2016 }
• Fan-Bundle-Planar Drawings of Graphs. Angelini, Patrizio; Bekos, Michael A.; Kaufmann, Michael; Kindermann, Philipp; Schneck, Thomas. In Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD’16), Vol. 9801 of Lecture Notes in Computer Science, Y. Hu, M. N{ö}llenburg (eds.), pp. 634–636. Springer-Verlag, 2016.
  • [ Abstract ]
  • [ BibTeX ]
  • [ URL ]
  • [ arxiv ]
  • [ slides ]
  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.

  @inproceedings{abkks-fbpdg-gd16poster, abstract = {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.}, author = {Angelini, Patrizio and Bekos, Michael A. and Kaufmann, Michael and Kindermann, Philipp and Schneck, Thomas}, booktitle = {Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD'16)}, editor = {Hu, Yifan and N{\"o}llenburg, Martin}, keywords = {bundle}, month = {09}, note = {Poster}, pages = {634–636}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Fan-Bundle-Planar Drawings of Graphs}, volume = 9801, year = 2016 }
• Strongly Monotone Drawings of Planar Graphs. Felsner, Stefan; Igamberdiev, Alexander; Kindermann, Philipp; Klemz, Boris; Mchedlidze, Tamara; Scheucher, Manfred. In Proceedings of the 32nd International Symposium on Computational Geometry (SoCG’16), Vol. 51 of LIPIcs, S. Fekete, A. Lubiw (eds.), pp. 37:1–37:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  A straight-line drawing of a graph is a \emph{monotone drawing} if for each pair of vertices there is a path which is monotonically increasing in some direction, and it is called a \emph{strongly 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.

  @inproceedings{fikkms-smdpg-socg16, abstract = {A straight-line drawing of a graph is a \emph{monotone drawing} if for each pair of vertices there is a path which is monotonically increasing in some direction, and it is called a \emph{strongly 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.}, author = {Felsner, Stefan and Igamberdiev, Alexander and Kindermann, Philipp and Klemz, Boris and Mchedlidze, Tamara and Scheucher, Manfred}, booktitle = {Proceedings of the 32nd International Symposium on Computational Geometry (SoCG'16)}, editor = {Fekete, S{\'a}ndor and Lubiw, Anna}, keywords = {monotone}, month = {06}, pages = {37:1–37:15}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, series = {LIPIcs}, title = {Strongly Monotone Drawings of Planar Graphs}, volume = 51, year = 2016 }
• On the Planar Split Thickness of Graphs. Eppstein, Davin; Kindermann, Philipp; Liotta, Giuseppe; Lubiw, Anna; Maignan, Aude; Mondal, Debajyoti; Vosoughpour, Hamideh; Whitesides, Sue; Wismath, Stephen. In Proceedings of the 12th Latin American Theoretical Informatics Symposium (LATIN’16), Vol. 9644 of Lecture Notes in Computer Science, E. Kranakis, G. Navarro, E. Ch{{á}}vez (eds.), pp. 403–415. Springer-Verlag, 2016.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  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.

  @inproceedings{ekkllmmvww-opstg-latin16, abstract = {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.}, author = {Eppstein, Davin and Kindermann, Philipp and Liotta, Giuseppe and Lubiw, Anna and Maignan, Aude and Mondal, Debajyoti and Vosoughpour, Hamideh and Whitesides, Sue and Wismath, Stephen}, booktitle = {Proceedings of the 12th Latin American Theoretical Informatics Symposium (LATIN'16)}, editor = {Kranakis, Evangelos and Navarro, Gonzalo and Ch{\'{a}}vez, Edgar}, keywords = {planar}, month = {04}, pages = {403–415}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {On the Planar Split Thickness of Graphs}, volume = 9644, year = 2016 }
• Strongly Monotone Drawings of Planar Graphs. Felsner, Stefan; Igamberdiev, Alexander; Kindermann, Philipp; Klemz, Boris; Mchedlidze, Tamara; Scheucher, Manfred. In Proceedings of the 32nd European Workshop on Computational Geometry (EuroCG’16), G. Barequet, E. Papadopoulou (eds.), pp. 59–62. Lugano, 2016.
  • [ Abstract ]
  • [ BibTeX ]
  • [ URL ]
  • [ arxiv ]
  • [ slides ]
  A straight-line drawing of a graph is a \emph{monotone drawing} if for each pair of vertices there is a path which is monotonically increasing in some direction, and it is called a \emph{strongly 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.

  @inproceedings{fikkms-smdpg-eurocg16, abstract = {A straight-line drawing of a graph is a \emph{monotone drawing} if for each pair of vertices there is a path which is monotonically increasing in some direction, and it is called a \emph{strongly 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.}, author = {Felsner, Stefan and Igamberdiev, Alexander and Kindermann, Philipp and Klemz, Boris and Mchedlidze, Tamara and Scheucher, Manfred}, booktitle = {Proceedings of the 32nd European Workshop on Computational Geometry (EuroCG'16)}, editor = {Barequet, Gill and Papadopoulou, Evanthia}, keywords = {monotone}, month = {03}, note = {Abstract}, pages = {59–62}, publisher = {Lugano}, title = {Strongly Monotone Drawings of Planar Graphs}, year = 2016 }
• Drawing Trees and Triangulations with Few Geometric Primitives. H{ü}ltenschmidt, Gregor; Kindermann, Philipp; Meulemans, Wouter; Schulz, Andr{é}. In Proceedings of the 32nd European Workshop on Computational Geometry (EuroCG’16), G. Barequet, E. Papadopoulou (eds.), pp. 55–58. Lugano, 2016.
  • [ Abstract ]
  • [ BibTeX ]
  • [ URL ]
  • [ arxiv ]
  • [ slides ]
  We define the \emph{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.

  @inproceedings{hkms-dttfg-eurocg16, abstract = {We define the \emph{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.}, author = {H{\"u}ltenschmidt, Gregor and Kindermann, Philipp and Meulemans, Wouter and Schulz, Andr{\'e}}, booktitle = {Proceedings of the 32nd European Workshop on Computational Geometry (EuroCG'16)}, editor = {Barequet, Gill and Papadopoulou, Evanthia}, keywords = {drawing}, month = {03}, note = {Abstract}, pages = {55–58}, publisher = {Lugano}, title = {Drawing Trees and Triangulations with Few Geometric Primitives}, year = 2016 }
• Windrose Planarity – Embedding Graphs with Direction-Constrained Edges. Angelini, Patrizio; Da Lozzo, Giordano; Di Battista, Giuseppe; Di Donato, Valentino; Kindermann, Philipp; Rote, Günter; Rutter, Ignaz. In Proceedings of the 27th Annual {ACM-SIAM} Symposium on Discrete Algorithms (SODA’16), R. Krauthgamer (ed.), pp. 985–996. SIAM, 2016.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  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.

  @inproceedings{adddkrr-wpegd-soda16, abstract = {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.}, author = {Angelini, Patrizio and Da Lozzo, Giordano and Di Battista, Giuseppe and Di Donato, Valentino and Kindermann, Philipp and Rote, Günter and Rutter, Ignaz}, booktitle = {Proceedings of the 27th Annual {ACM-SIAM} Symposium on Discrete Algorithms (SODA'16)}, editor = {Krauthgamer, Robert}, keywords = {planar}, month = {02}, pages = {985–996}, publisher = {SIAM}, title = {Windrose Planarity – Embedding Graphs with Direction-Constrained Edges}, year = 2016 }
• Recognizing and Drawing IC-Planar Graphs. Brandenburg, Franz J.; Didimo, Walter; Evans, William S.; Kindermann, Philipp; Liotta, Giuseppe; Montecchiani, Fabrizio. In Proceedings of the 23rd International Symposium on Graph Drawing & Network Visualization (GD’15), Vol. 9411 of Lecture Notes in Computer Science, E. Di Giacomo, A. Lubiw (eds.), pp. 295–308. Springer-Verlag, 2015.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  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.

  @inproceedings{bdeklm-rdicp-gd15, abstract = {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.}, author = {Brandenburg, Franz J. and Didimo, Walter and Evans, William S. and Kindermann, Philipp and Liotta, Giuseppe and Montecchiani, Fabrizio}, booktitle = {Proceedings of the 23rd International Symposium on Graph Drawing & Network Visualization (GD’15)}, editor = {Di Giacomo, Emilio and Lubiw, Anna}, keywords = {drawings}, month = {09}, pages = {295–308}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Recognizing and Drawing IC-Planar Graphs}, volume = 9411, year = 2015 }
• Simultaneous Drawing of Planar Graphs with Right-Angle Crossings and Few Bends. Bekos, Michael A.; van Dijk, Thomas C.; Kindermann, Philipp; Wolff, Alexander. In Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM’15), Vol. 8973 of Lecture Notes in Computer Science, M. Rahman, E. Tomita (eds.), pp. 222–233. Springer-Verlag, 2015.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  Given two planar graphs that are defined on the same set of vertices, \emph{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.

  @inproceedings{bdkw-sdrac-14, abstract = {Given two planar graphs that are defined on the same set of vertices, \emph{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.}, author = {Bekos, Michael A. and van Dijk, Thomas C. and Kindermann, Philipp and Wolff, Alexander}, booktitle = {Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM'15)}, editor = {Rahman, M.S. and Tomita, E.}, keywords = {myown}, month = {02}, pages = {222–233}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Simultaneous Drawing of Planar Graphs with Right-Angle Crossings and Few Bends}, volume = 8973, year = 2015 }
• Solving Optimization Problems on Orthogonal Ray Graphs. Chaplick, Steven; Kindermann, Philipp; Lipp, Fabian; Wolff, Alexander. In Proceedings of the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG’15), p. 2 pp. 2015.
  • [ Abstract ]
  • [ BibTeX ]
  • [ URL ]
  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.

  @inproceedings{cklw-sopor-JCDCGG15, abstract = {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.}, author = {Chaplick, Steven and Kindermann, Philipp and Lipp, Fabian and Wolff, Alexander}, booktitle = {Proceedings of the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG’15)}, keywords = {myown}, month = {09}, note = {Abstract}, pages = {2 pp.}, title = {Solving Optimization Problems on Orthogonal Ray Graphs}, year = 2015 }
• Minimum Rectilinear Polygons for Given Angle Sequences. Evans, William S.; Fleszar, Krzysztof; Kindermann, Philipp; Saeedi, Noushin; Shin, Chan-Su; Wolff, Alexander. In Proceedings of the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG’15), Vol. 9943 of Lecture Notes in Computer Science, pp. 105–119. Springer-Verlag, 2015.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  A rectilinear 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.

  @inproceedings{efkssw-mrpga-JCDCGG15, abstract = {A rectilinear 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.}, author = {Evans, William S. and Fleszar, Krzysztof and Kindermann, Philipp and Saeedi, Noushin and Shin, Chan-Su and Wolff, Alexander}, booktitle = {Proceedings of the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG’15)}, keywords = {myown}, month = {09}, pages = {105–119}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Minimum Rectilinear Polygons for Given Angle Sequences}, volume = 9943, year = 2015 }
• Graph Drawing Contest Report. Kindermann, Philipp; L{{ö}}ffler, Maarten; Nachmanson, Lev; Rutter, Ignaz. In Proceedings of the 23rd International Symposium on Graph Drawing and Network Visualization (GD’15), Vol. 9411 of Lecture Notes in Computer Science, E. D. Giacomo, A. Lubiw (eds.), pp. 531–537. Springer, 2015.
  • [ BibTeX ]
  • [ URL ]
  • [ DOI ]
  • [ slides ]
  @inproceedings{klnr-gdcr-gd15, author = {Kindermann, Philipp and L{\"{o}}ffler, Maarten and Nachmanson, Lev and Rutter, Ignaz}, booktitle = {Proceedings of the 23rd International Symposium on Graph Drawing and Network Visualization (GD'15)}, editor = {Giacomo, Emilio Di and Lubiw, Anna}, keywords = {contest}, month = {09}, pages = {531–537}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Graph Drawing Contest Report}, volume = 9411, year = 2015 }
• Colored Non-Crossing Euclidean Steiner Forest. Bereg, Sergey; Fleszar, Krzysztof; Kindermann, Philipp; Pupyrev, Sergey; Spoerhase, Joachim; Wolff, Alexander. In Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC’15), Vol. 9472 of Lecture Notes in Computer Science, K. Elbassioni, K. Makino (eds.), pp. 429–441. Springer-Verlag, 2015.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  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$.

  @inproceedings{bfkpsw-cnesf-isaac15, abstract = {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$.}, author = {Bereg, Sergey and Fleszar, Krzysztof and Kindermann, Philipp and Pupyrev, Sergey and Spoerhase, Joachim and Wolff, Alexander}, booktitle = {Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC'15)}, editor = {Elbassioni, Khaled and Makino, Kazuhisa}, keywords = {Steiner}, month = 12, pages = {429–441}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Colored Non-Crossing Euclidean Steiner Forest}, volume = 9472, year = 2015 }
• Luatodonotes: Boundary Labeling for Annotations in Texts. Kindermann, Philipp; Lipp, Fabian; Wolff, Alexander. In Proceedings of the 22nd International Symposium on Graph Drawing (GD’14), Vol. 8871 of Lecture Notes in Computer Science, C. Duncan, A. Symvonis (eds.), pp. 76–88. Springer-Verlag, 2014.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ slides ]
  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 \emph{leaders}). Problems of this type have been studied under the name \emph{boundary 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.

  @inproceedings{klw-lblat-gd14, abstract = {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 \emph{leaders}). Problems of this type have been studied under the name \emph{boundary labeling}. We consider various leader types (straight-line, rectilinear, and B\'ezier) 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.}, author = {Kindermann, Philipp and Lipp, Fabian and Wolff, Alexander}, booktitle = {Proceedings of the 22nd International Symposium on Graph Drawing (GD'14)}, editor = {Duncan, C. and Symvonis, A.}, keywords = {myown}, month = {09}, pages = {76–88}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Luatodonotes: Boundary Labeling for Annotations in Texts}, volume = 8871, year = 2014 }
• Simultaneous Drawing of Planar Graphs with Right-Angle Crossings and Few Bends. Bekos, Michael A.; van Dijk, Thomas C.; Kindermann, Philipp; Wolff, Alexander. In Proceedings of the 22nd International Symposium on Graph Drawing (GD’14), Vol. 8871 of Lecture Notes in Computer Science, C. Duncan, A. Symvonis (eds.), pp. 515–516. Springer-Verlag, 2014.
  • [ Abstract ]
  • [ BibTeX ]
  • [ URL ]
  • [ arxiv ]
  • [ slides ]
  Given two planar graphs that are defined on the same set of vertices, \emph{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.

  @inproceedings{bekos2014simultaneous, abstract = {Given two planar graphs that are defined on the same set of vertices, \emph{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.}, author = {Bekos, Michael A. and van Dijk, Thomas C. and Kindermann, Philipp and Wolff, Alexander}, booktitle = {Proceedings of the 22nd International Symposium on Graph Drawing (GD'14)}, editor = {Duncan, C. and Symvonis, A.}, howpublished = {Poster}, keywords = {myown}, month = {09}, note = {Poster}, pages = {515–516}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Simultaneous Drawing of Planar Graphs with Right-Angle Crossings and Few Bends}, volume = 8871, year = 2014 }
• On Monotone Drawings of Trees. Kindermann, Philipp; Schulz, André; Spoerhase, Joachim; Wolff, Alexander. In Proceedings of the 22nd International Symposium on Graph Drawing (GD’14), Vol. 8871 of Lecture Notes in Computer Science, C. Duncan, A. Symvonis (eds.), pp. 488–500. Springer-Verlag, 2014.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  A crossing-free straight-line drawing of a graph is \emph{monotone} if there is a monotone path between any pair of vertices with respect to \emph{some} 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 \emph{convex}, 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 \emph{strongly 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.

  @inproceedings{kssw-omdt-14, abstract = {A crossing-free straight-line drawing of a graph is \emph{monotone} if there is a monotone path between any pair of vertices with respect to \emph{some} 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 \emph{convex}, 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 \emph{strongly 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.}, author = {Kindermann, Philipp and Schulz, André and Spoerhase, Joachim and Wolff, Alexander}, booktitle = {Proceedings of the 22nd International Symposium on Graph Drawing (GD'14)}, editor = {Duncan, C. and Symvonis, A.}, keywords = {monotone}, month = {09}, pages = {488–500}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {On Monotone Drawings of Trees}, volume = 8871, year = 2014 }
• Improved Approximation Algorithms for Box Contact Representations. Bekos, Michael A.; van Dijk, Thomas C.; Fink, Martin; Kindermann, Philipp; Kobourov, Stephen; Pupyrev, Sergey; Spoerhase, Joachim; Wolff, Alexander. In Proceedings of the 22nd European Symposium on Algorithms (ESA’14), Vol. 8737 of Lecture Notes in Computer Science, A. S. Schulz, D. Wagner (eds.), pp. 87–99. Springer-Verlag, 2014.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  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 \textsc{Contact Representation of Word Networks} (\textsc{Crown}) since it formalizes the geometric problem behind drawing word clouds in which semantically related words are close to each other. \textsc{Crown} is known to be NP-hard, and there are approximation algorithms for certain graph classes for the optimization version, \textsc{Max-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.

  @inproceedings{bdfkkpsw-iaabcr-ESA14, abstract = {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 \textsc{Contact Representation of Word Networks} (\textsc{Crown}) since it formalizes the geometric problem behind drawing word clouds in which semantically related words are close to each other. \textsc{Crown} is known to be NP-hard, and there are approximation algorithms for certain graph classes for the optimization version, \textsc{Max-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.}, author = {Bekos, Michael A. and van Dijk, Thomas C. and Fink, Martin and Kindermann, Philipp and Kobourov, Stephen and Pupyrev, Sergey and Spoerhase, Joachim and Wolff, Alexander}, booktitle = {Proceedings of the 22nd European Symposium on Algorithms (ESA'14)}, editor = {Schulz, Andreas S. and Wagner, Dorothea}, keywords = {myown}, month = {09}, pages = {87–99}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Improved Approximation Algorithms for Box Contact Representations}, volume = 8737, year = 2014 }
• Smooth Orthogonal Drawings of Planar Graphs. Alam, Md. Jawaherul; Bekos, Michael A.; Kaufmann, Michael; Kindermann, Philipp; Kobourov, Stephen G.; Wolff, Alexander. In Proc. 11th Latin American Sympos. on Theoretical Informatics (LATIN’14), Vol. 8392 of Lecture Notes in Computer Science, A. Pardo, A. Viola (eds.), pp. 144–155. Springer-Verlag, 2014.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  In \emph{smooth 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 \emph{edge complexity}, that is, with few segments per edge. We say that a graph has \emph{smooth 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.

  @inproceedings{abkkkw-sodpg-latin14, abstract = {In \emph{smooth 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 \emph{edge complexity}, that is, with few segments per edge. We say that a graph has \emph{smooth 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.}, author = {Alam, Md. Jawaherul and Bekos, Michael A. and Kaufmann, Michael and Kindermann, Philipp and Kobourov, Stephen G. and Wolff, Alexander}, booktitle = {Proc. 11th Latin American Sympos. on Theoretical Informatics (LATIN'14)}, editor = {Pardo, A. and Viola, A.}, keywords = {myown}, month = {04}, pages = {144–155}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Smooth Orthogonal Drawings of Planar Graphs}, volume = 8392, year = 2014 }
• Two-Sided Boundary Labeling with Adjacent Sides. Kindermann, Philipp; Niedermann, Benjamin; Rutter, Ignaz; Schaefer, Marcus; Schulz, Andr{é}; Wolff, Alexander. In Proceedings of the 13th International Algorithms and Data Structure Symposium (WADS’13), Vol. 8037 of Lecture Notes in Computer Science, F. Dehne, R. Solis-Oba, J.-R. Sack (eds.), pp. 463–474. Springer-Verlag, 2013.
  • [ Abstract ]
  • [ BibTeX ]
  • [ DOI ]
  • [ arxiv ]
  • [ slides ]
  In the \emph{Boundary Labeling} problem, we are given a set of $n$ points, referred to as \emph{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 \emph{leaders}, with at most one bend. In this paper, we study the problem \emph{Two-Sided Boundary Labeling with Adjacent Sides}, where labels lie on two adjacent 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 that labels lie on one side or on two opposite sides of $R$ (where a crossing-free solution always exists). For the more difficult case where labels lie on adjacent sides, we show how to compute crossing-free leader layouts that maximize the number of labeled points or minimize the total leader length.

  @inproceedings{knrssw-2sbla-wads13, abstract = {In the \emph{Boundary Labeling} problem, we are given a set of $n$ points, referred to as \emph{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 \emph{leaders}, with at most one bend. In this paper, we study the problem \emph{Two-Sided Boundary Labeling with Adjacent Sides}, where labels lie on two adjacent 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 that labels lie on one side or on two opposite sides of $R$ (where a crossing-free solution always exists). For the more difficult case where labels lie on adjacent sides, we show how to compute crossing-free leader layouts that maximize the number of labeled points or minimize the total leader length.}, author = {Kindermann, Philipp and Niedermann, Benjamin and Rutter, Ignaz and Schaefer, Marcus and Schulz, Andr{\'e} and Wolff, Alexander}, booktitle = {Proceedings of the 13th International Algorithms and Data Structure Symposium (WADS'13)}, editor = {Dehne, F. and Solis-Oba, R. and Sack, J.-R.}, keywords = {myown}, month = {08}, pages = {463–474}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Two-Sided Boundary Labeling with Adjacent Sides}, volume = 8037, year = 2013 }
• Two-Sided Boundary Labeling with Adjacent Sides. Kindermann, Philipp; Niedermann, Benjamin; Rutter, Ignaz; Schaefer, Marcus; Schulz, Andr{é}; Wolff, Alexander. In Proceedings of the 29th European Workshop on Computational Geometry (EuroCG’13), S. Fekete (ed.), pp. 233–236. Braunschweig, 2013.
  • [ Abstract ]
  • [ BibTeX ]
  • [ URL ]
  • [ arxiv ]
  • [ slides ]
  In the \emph{Boundary Labeling} problem, we are given a set of~$n$ points, referred to as \emph{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 polygonal paths, so-called \emph{leaders}. In this paper, we study the \emph{Two-Sided Boundary Labeling with Adjacent Sides} problem, with labels lying on two adjacent sides of the enclosing rectangle. We restrict ourselves to rectilinear leaders with at most one bend. We present a polynomial-time algorithm that computes a crossing-free leader layout if one exists. So far, such an algorithm has only been known for the simpler cases that labels lie on one side or on two opposite sides of~$R$ (where a crossing-free solution always exists).

  @inproceedings{knrssw-2sbla-eurocg13, abstract = {In the \emph{Boundary Labeling} problem, we are given a set of $n$ points, referred to as \emph{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 polygonal paths, so-called \emph{leaders}. In this paper, we study the \emph{Two-Sided Boundary Labeling with Adjacent Sides} problem, with labels lying on two adjacent sides of the enclosing rectangle. We restrict ourselves to rectilinear leaders with at most one bend. We present a polynomial-time algorithm that computes a crossing-free leader layout if one exists. So far, such an algorithm has only been known for the simpler cases that labels lie on one side or on two opposite sides of $R$ (where a crossing-free solution always exists).}, address = {Braunschweig}, author = {Kindermann, Philipp and Niedermann, Benjamin and Rutter, Ignaz and Schaefer, Marcus and Schulz, Andr{\'e} and Wolff, Alexander}, booktitle = {Proceedings of the 29th European Workshop on Computational Geometry (EuroCG'13)}, editor = {Fekete, S{\'a}ndor}, keywords = {myown}, month = {03}, pages = {233–236}, title = {Two-Sided Boundary Labeling with Adjacent Sides}, year = 2013 }

• Vehicle Routing with Time Constraints and Different Vehicles. Technical Report (Master thesis), . Kindermann, Philipp. Master thesis. Lehrstuhl für Informatik I, Universität Würzburg, 2011, October.
  • [ BibTeX ]
  • [ URL ]
  @mastersthesis{k-vrtcdv-11, author = {Kindermann, Philipp}, keywords = {diplomarbeit}, month = 10, note = {(German)}, school = {Lehrstuhl f\"ur Informatik I, Universit\"at W\"urzburg}, title = {Vehicle Routing with Time Constraints and Different Vehicles}, type = {Diplomarbeit}, year = 2011 }

• Angular Schematization in Graph Drawing. Technical Report (PhD dissertation), . Kindermann, Philipp. PhD dissertation. Fakultät für Mathematik und Informatik, Universität Würzburg, 2015, June.
  • [ Abstract ]
  • [ BibTeX ]
  • [ URL ]
  • [ slides ]
  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.

  @phdthesis{k-asgd-PHD15, abstract = {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.}, author = {Kindermann, Philipp}, keywords = {graph}, month = {06}, school = {Fakultät für Mathematik und Informatik, Universität Würzburg}, title = {Angular Schematization in Graph Drawing}, year = 2015 }