Ignaz Rutter

Ignaz Rutter

Auto-generated profile, based on publicly available information

Ignaz Rutter

University of Passau, Passau, Germany

Research Focus & Metrics

Academic Career Length

19Years (2008-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
8 December 2015 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
TBThomas Bläsius
Thomas Bläsius
IRIgnaz Rutter
Ignaz Rutter
In this article, we define and study the new problem of S imultaneous PQ-O rdering . Its input consists of a set of PQ-trees, which represent sets of circular orders of their leaves, together with a set of child-parent relations between these PQ-trees, such that the leaves of the child form a subset of the leaves of the parent. S imultaneous PQ-O rdering asks whether orders of the leaves of each of the trees can be chosen simultaneously ; that is, for every child-parent relation, the order chosen for the parent is an extension of the order chosen for the child. We show that S imultaneous PQ-O rdering is NP -complete in general, and we identify a family of instances that can be solved efficiently, the 2-fixed instances . We show that this result serves as a framework for several other problems that can be formulated as instances of S imultaneous PQ-O rdering . In particular, we give linear-time algorithms for recognizing simultaneous interval graphs and extending partial interval representations. Moreover, we obtain a linear-time algorithm for P artially PQ-C onstrained P lanarity for biconnected graphs, which asks for a planar embedding in the presence of PQ-trees that restrict the possible orderings of edges around vertices, and a quadratic-time algorithm for S imultaneous E mbedding with F ixed E dges for biconnected graphs with a connected intersection. Both results can be extended to the case where the input graphs are not necessarily biconnected but have the property that each cutvertex is contained in at most two nontrivial blocks. This includes, for example, the case where both graphs have a maximum degree of 5.

13 April 2015 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
PAPatrizio Angelini
Patrizio Angelini
GBGiuseppe Di Battista
Giuseppe Di Battista
FFFabrizio Frati
Fabrizio Frati
VJVít Jelínek
Vít Jelínek
JKJan Kratochvíl
Jan Kratochvíl
IRIgnaz Rutter
Ignaz Rutter
We study the following problem: given a planar graph G and a planar drawing (embedding) of a subgraph of G , can such a drawing be extended to a planar drawing of the entire graph G ? This problem fits the paradigm of extending a partial solution for a problem to a complete one, which has been studied before in many different settings. Unlike many cases, in which the presence of a partial solution in the input makes an otherwise easy problem hard, we show that the planarity question remains polynomial-time solvable. Our algorithm is based on several combinatorial lemmas, which show that the planarity of partially embedded graphs exhibits the ‘TONCAS’ behavior “the obvious necessary conditions for planarity are also sufficient.” These conditions are expressed in terms of the interplay between (1) the rotation system and containment relationships between cycles and (2) the decomposition of a graph into its connected, biconnected, and triconnected components. This implies that no dynamic programming is needed for a decision algorithm and that the elements of the decomposition can be processed independently. Further, by equipping the components of the decomposition with suitable data structures and by carefully splitting the problem into simpler subproblems, we make our algorithm run in linear time. Finally, we consider several generalizations of the problem, such as minimizing the number of edges of the partial embedding that need to be rerouted to extend it, and argue that they are NP-hard. We also apply our algorithm to the simultaneous graph drawing problem Simultaneous Embedding with Fixed Edges (Sefe) . There we obtain a linear-time algorithm for the case that one of the input graphs or the common graph has a fixed planar embedding.

1 July 2012 in Journal of Discrete Algorithms
Verified
Journal Article
Closed access
PAPatrizio Angelini
Patrizio Angelini
GBGiuseppe Di Battista
Giuseppe Di Battista
FFFabrizio Frati
Fabrizio Frati
MPMaurizio Patrignani
Maurizio Patrignani
IRIgnaz Rutter
Ignaz Rutter

1 October 2018 in Theoretical Computer Science
Verified
Journal Article
Closed access
SBSang Won Bae
Sang Won Bae
JBJean-Francois Baffier
Jean-Francois Baffier
JCJinhee Chun
Jinhee Chun
PEPeter Eades
Peter Eades
KEKord Eickmeyer
Kord Eickmeyer
CTCsaba D. Tóth
Csaba D. Tóth

1 May 2013 in Computational Geometry
Verified
Journal Article
Closed access
VJVít Jelínek
Vít Jelínek
JKJan Kratochvíl
Jan Kratochvíl
IRIgnaz Rutter
Ignaz Rutter

25 February 2016 in Algorithmica
Verified
Journal Article
Closed access
PDF file
PKPavel Klavík
Pavel Klavík
JKJan Kratochvíl
Jan Kratochvíl
YOYota Otachi
Yota Otachi
IRIgnaz Rutter
Ignaz Rutter
TSToshiki Saitoh
Toshiki Saitoh
TVTomáš Vyskočil
Tomáš Vyskočil