IRIgnaz Rutter

Ignaz Rutter

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Ignaz Rutter has a total of 201 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Simple Realizability of Abstract Topological Graphs

    by Giordano Da Lozzo, Walter Didimo, Fabrizio Montecchiani, Miriam Münch, Maurizio Patrignani, Ignaz Rutter

    An abstract topological graph ( AT-graph ) is a pair $$A=(G,\mathcal {X})$$ A = ( G , X ) , where $$G=(V,E)$$ G = ( V , E ) is a graph and $$\mathcal {X} \subseteq \left( {\begin{array}{c}E\\ 2\end{array}}\right) $$ X ⊆ E 2 is a set of pairs of edges of G . A realization of A is a drawing $$\Gamma _A$$ Γ A of G in the plane such that any two edges $$e_1,e_2$$ e 1 , e 2 of G cross in $$\Gamma _A$$ Γ A if and only if $$(e_1,e_2) \in \mathcal {X} $$ ( e 1 , e 2 ) ∈ X ; $$\Gamma _A$$ Γ A is simple if any two edges intersect at most once (either at a common endpoint or at a proper crossing). The AT-graph Realizability ( ATR ) problem asks whether an input AT-graph admits a realization. The version of this problem that requires a simple realization is called Simple AT-graph Realizability ( SATR ). It is a classic result that both ATR and SATR are -complete [18, 21]. In this paper, we study the SATR problem from a new structural perspective. More precisely, we consider the size $$\mathrm {\lambda }(A)$$ λ ( A ) of the largest connected component of the crossing graph of any realization of A , i.e., the graph $$\mathcal{C}(A) = (E, \mathcal {X})$$ C ( A ) = ( E , X ) . This parameter represents a natural way to measure the level of interplay among edge crossings. First, we prove that SATR is -complete when $$\mathrm {\lambda }(A) \ge 6$$ λ ( A ) ≥ 6 . On the positive side, we give an optimal linear-time algorithm that solves SATR when $$\mathrm {\lambda }(A) \le 3$$ λ ( A ) ≤ 3 and returns a simple realization if one exists. Our algorithm is based on several ingredients, in particular the reduction to a new embedding problem subject to constraints that require certain pairs of edges to alternate (in the rotation system), and a sequence of transformations that exploit the interplay between alternation constraints and the SPQR-tree and PQ-tree data structures to eventually arrive at a simpler embedding problem that can be solved with standard techniques.

  • Open Access

    Tight Runtime Bounds for Evolutionary Algorithms on Sorting and Crossing Minimisation for Layered Graph Drawings

    by Jakob Baumann, Ignaz Rutter, Dirk Sudholt

    Graph Drawing aims to make graphs visually comprehensible while faithfully representing their structure. In layered drawings, each vertex is drawn on one of k given horizontal lines and edges are drawn as y -monotone curves. A key ingredient for constructing such drawings is the One-Sided Bipartite Crossing Minimisation (OBCM) problem: given two layers of a bipartite graph and a fixed horizontal order of the vertices on the first layer, the task is to order the vertices on the second layer to minimise the number of edge crossings. We analyse the performance of simple evolutionary algorithms for OBCM and compare different operators for permutations: exchanging two elements, swapping adjacent elements and jumping an element to a new position. We show that on instances that can be drawn crossing-free, OBCM corresponds to a generalised sorting problem. We provide novel and tight lower bounds of $$\Omega (n^2 \log n)$$ for sorting with exchanges and jumps, respectively. This solves a long-standing open problem by Scharnow, Tinnefeld, and Wegener (J. Math. Model. Algorithm 3(4):349–366, 2005). For the simplest and cheapest mutation operator, swap (swapping adjacent elements), we give a tight runtime bound of $$\Theta (n^2)$$ via a parallel BubbleSort algorithm and a delay sequence argument. This proves that the simplest and cheapest mutation operator is also the fastest for sorting and solving planar OBCM instances.

  • Open Access

    Crossing Number of Simple 3-Plane Drawings

    by Torsten Ueckerdt, Miriam Goetze, Michael Hoffmann, Ignaz Rutter

    We study 3-plane drawings, that is, drawings of graphs in which every edge has at most three crossings. We show how the recently developed Density Formula for topological drawings of graphs [9] can be used to count the crossings in terms of the number n of vertices. As a main result, we show that every 3-plane drawing has at most 5.5(n − 2) crossings, which is tight. In particular, it follows that every 3-planar graph on n vertices has crossing number at most 5.5n, which improves upon a recent bound [3] of 6.6n. To apply the Density Formula, we carefully analyze the interplay between certain configurations of cells in a 3-plane drawing. As a by-product, we also obtain an alternative proof for the known statement that every 3-planar graph has at most 5.5(n − 2) edges.

  • Open Access

    Constrained outer-string representations

    by Therese Biedl, Sabine Cornelsen, Jan Kratochvíl, Ignaz Rutter

  • Open Access

    Weakly leveled planarity with bounded span

    by Michael A. Bekos, Giordano Da Lozzo, Fabrizio Frati, Siddharth Gupta, Philipp Kindermann, Giuseppe Liotta, Ignaz Rutter, Ioannis G. Tollis

  • Open Access

    The Price of Upwardness

    by Patrizio Angelini, Therese Biedl, Markus Chimani, Sabine Cornelsen, Giordano Da Lozzo, Seok-Hee Hong, Giuseppe Liotta, Maurizio Patrignani, Sergey Pupyrev, Ignaz Rutter, et al.

    Not every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyond planarity by considering upward $k$-planar drawings of DAGs in which the edges are monotonically increasing in a common direction and every edge is crossed at most $k$ times for some integer $k \ge 1$. We show that the number of crossings per edge in a monotone drawing is in general unbounded for the class of bipartite outerplanar, cubic, or bounded pathwidth DAGs. However, it is at most two for outerpaths and it is at most quadratic in the bandwidth in general. From the computational point of view, we prove that testing upward-$k$-planarity is NP-complete already for $k=1$ and even for restricted instances for which upward planarity testing is polynomial. On the positive side, we can decide in linear time whether a single-source DAG admits an upward 1-planar drawing in which all vertices are incident to the outer face.This is the full version of a paper that appeared in the Proc. 32nd Int. Symp. Graph Drawing & Network Visualization (GD 2024)


  • Open Access

    Constrained Planarity in Practice -- Engineering the Synchronized Planarity Algorithm

    by Simon Dominik Fink, Ignaz Rutter

    In the constrained planarity setting, we ask whether a graph admits a planar drawing that additionally satisfies a given set of constraints. These constraints are often derived from very natural problems; prominent examples are Level Planarity, where vertices have to lie on given horizontal lines indicating a hierarchy, and Clustered Planarity, where we additionally draw the boundaries of clusters which recursively group the vertices in a crossing-free manner. Despite receiving significant amount of attention and substantial theoretical progress on these problems, only very few of the found solutions have been put into practice and evaluated experimentally. In this paper, we describe our implementation of the recent quadratic-time algorithm by Bläsius et al. [TALG 2023] for solving the problem Synchronized Planarity, which can be seen as a common generalization of several constrained planarity problems, including the aforementioned ones. Our experimental evaluation on an existing benchmark set shows that even our baseline implementation outperforms all competitors by at least an order of magnitude. We systematically investigate the degrees of freedom in the implementation of the Synchronized Planarity algorithm for larger instances and propose several modifications that further improve the performance. Altogether, this allows us to solve instances with up to 100 vertices in milliseconds and instances with up to 100 000 vertices within a few minutes.

  • Open Access

    Crossing Number of 3-Plane Drawings

    by Miriam Goetze, Michael Hoffmann, Ignaz Rutter, Torsten Ueckerdt

    We study 3-plane drawings, that is, drawings of graphs in which every edge has at most three crossings. We show how the recently developed Density Formula for topological drawings of graphs (KKKRSU GD 2024) can be used to count the crossings in terms of the number $n$ of vertices. As a main result, we show that every 3-plane drawing has at most $5.5(n-2)$ crossings, which is tight. In particular, it follows that every 3-planar graph on $n$ vertices has crossing number at most $5.5n$, which improves upon a recent bound (BBBDHKMOW GD 2024) of $6.6n$. To apply the Density Formula, we carefully analyze the interplay between certain configurations of cells in a 3-plane drawing. As a by-product, we also obtain an alternative proof for the known statement that every 3-planar graph has at most $5.5(n-2)$ edges.

  • Open Access

    Simultaneous Representation of Proper and Unit Interval Graphs

    by Ignaz Rutter, Darren Strash, Peter Stumpf, Michael Vollmer

    In a confluence of combinatorics and geometry, simultaneous representations provide a way to realize combinatorial objects that share common structure. A standard case in the study of simultaneous representations is the sunflower case where all objects share the same common structure. While the recognition problem for general simultaneous interval graphs—the simultaneous version of arguably one of the most well-studied graph classes—is NP-complete, the complexity of the sunflower case for three or more simultaneous interval graphs is currently open. In this work we settle this question for proper interval graphs. We give an algorithm to recognize simultaneous proper interval graphs in linear time in the sunflower case where we allow any number of simultaneous graphs. Simultaneous unit interval graphs are much more ‘rigid’ and therefore have less freedom in their representation. We show they can be recognized in time $$\mathcal {O}(|V|\cdot |E|)$$ O ( | V | · | E | ) for any number of simultaneous graphs in the sunflower case where $$G=(V,E)$$ G = ( V , E ) is the union of the simultaneous graphs. We further show that both recognition problems are in general NP-complete if the number of simultaneous graphs is not fixed. The restriction to the sunflower case is in this sense necessary.