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


Ioannis G. Tollis has a total of 35 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • 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

    Unit Edge-Length Rectilinear Drawings with Crossings and Rectangular Faces

    by Patrizio Angelini, Carla Binucci, Giuseppe Di Battista, Emilio Di Giacomo, Walter Didimo, Fabrizio Grosso, Giacomo Ortali, Ioannis G. Tollis

    Unit edge-length drawings, rectilinear drawings (where each edge is either a horizontal or a vertical segment), and rectangular face drawings are among the most studied subjects in Graph Drawing. However, most of the literature on these topics refers to planar graphs and planar drawings. In this paper we study drawings with all the above nice properties but that can have edge crossings; we call them Unit Edge length Rectilinear drawings with Rectangular Faces (UER-RF drawings). We consider crossings as dummy vertices and apply the unit edge-length convention to the edge segments connecting any two (real or dummy) vertices. Note that UER-RF drawings are grid drawings (vertices are placed at distinct integer coordinates), which is another classical requirement of graph visualizations. We present several efficient and easily implementable algorithms for recognizing graphs that admit UER-RF drawings and for constructing such drawings if they exist. We consider restrictions on the degree of the vertices or on the size of the faces. For each type of restriction, we consider both the general unconstrained setting and a setting in which either the external boundary of the drawing is fixed or the rotation system of the graph is fixed as part of the input.

  • Open Access

    Parameterized Linear Time Transitive Closure

    by Giorgos Kritikakis, Ioannis G Tollis

    Inquiries such as whether a task A depends on a task B, whether an author A has been influenced by a paper B, whether a certain protein is associated with a specific biological process or molecular function, or whether class A inherits from class B, are just a few examples of inquiries that can be modeled as reachability queries on a network (Directed Graph). Digital systems answer myriad such inquiries every day. In this paper, we discuss the transitive closure problem. We focus on applicable solutions that enable us to answer queries fast, in constant time, and can serve in real-world applications. In contrast to the majority of research on this topic that revolves around the construction of a two-dimensional adjacency matrix, we present an approach that builds a reachability indexing scheme. This scheme enables us to answer queries in constant time and can be built in parameterized linear time. In addition, it captures a compressed data structure. Our approach and algorithms are validated by extensive experiments that shed light on the factors that play a key role in this problem. To stress the efficiency of this solution and demonstrate the potential to apply our approach to important problems, we use it to speed up Fulkerson's method for finding the width of a DAG. Our results challenge the prevailing belief, reiterated over the last thirty years, regarding the efficiency of this method. Our approach is based on the concept of chain decomposition. Before we delve into its description, we introduce, analyze, and utilize a chain decomposition algorithm. Furthermore, we explore how chain decomposition can facilitate transitive closure solutions introducing a general purpose linear time reduction technique that removes a large subset of transitive edges given any chain decomposition.

  • Open Access

    Experiments and a User Study for Hierarchical Drawings of Graphs

    by Panagiotis Lionakis, Giorgos Kritikakis, Ioannis G. Tollis

    We present a detailed hierarchical graph drawing technique that is based on the Path Based Framework (PBF) . Extensive edge bundling is applied to draw all edges of the graph and the height of the drawing is minimized using compaction. We present experimental results and a user study for hierarchical drawings of graphs that show the usefulness of the new drawing technique. The drawings produced by the new framework are compared to drawings produced by the well known Sugiyama framework in terms of area, number of bends, number of crossings, and execution time. The new algorithm runs very fast and produces drawings that are readable and more efficient in terms of area and number of bends. Furthermore, since there are advantages (and disadvantages) to both frameworks, we performed a user study. The results show that the drawings produced by the new framework are well received in terms of clarity, readability, and usability. Hence, the new technique offers an interesting alternative to drawing hierarchical graphs, and is especially useful in applications where user defined paths are important and need to be highlighted.


  • Computing a Feedback Arc Set Using PageRank

    by Vasileios Geladaris, Panagiotis Lionakis, Ioannis G. Tollis


  • Open Access

    Fast and Practical DAG Decomposition with Reachability Applications

    by Giorgos Kritikakis, Ioannis G. Tollis

    We present practical linear and almost linear-time algorithms to compute a chain decomposition of a directed acyclic graph (DAG), $G=(V,E)$. The number of vertex-disjoint chains computed is very close to the minimum. The time complexity of our algorithm is $O(|E|+c*l)$, where $c$ is the number of path concatenations and $l$ is the length of a longest path of the graph. We give a comprehensive explanation on factors $c$ and $l$ in the following sections. Our techniques have important applications in many areas, including the design of faster practical transitive closure algorithms. We observe that $|E_{red}|\leq width*|V|$ ($E_{red}$: non-transitive edges) and show how to find a substantially large subset of $E_{tr}$ (transitive edges) using a chain decomposition in linear time, without calculating the transitive closure. Our extensive experimental results show the interplay between the width, $E_{red}$, $E_{tr}$ in various models of graphs. We show how to compute a reachability indexing scheme in $O(k_c*|E_{red}|)$ time, where $k_c$ is the number of chains and $|E_{red}|$ is the number of non-transitive edges. This scheme can answer reachabilitiy queries in constant time. The space complexity of the scheme is $O(k_c*|V|)$. The experimental results reveal that our methods are even better in practice than the theoretical bounds imply, indicating how fast chain decomposition algorithms can be applied to the transitive closure problem.

  • Open Access

    Computing a Feedback Arc Set Using PageRank

    by Vasileios Geladaris, Panagiotis Lionakis, Ioannis G. Tollis

    We present a new heuristic algorithm for computing a minimum Feedback Arc Set in directed graphs. The new technique produces solutions that are better than the ones produced by the best previously known heuristics, often reducing the FAS size by more than 50%. It is based on computing the PageRank score of the nodes of the directed line graph of the input directed graph. Although the time required by our heuristic is heavily influenced by the size of the produced line graph, our experimental results show that it runs very fast even for very large graphs used in graph drawing.

  • Open Access

    Computing Weak Dominance Drawings with Minimum Number of Fips

    by Giacomo Ortali, Ioannis G. Tollis

    A weak dominance drawing $\Gamma$ of a DAG $G=(V,E)$, is a $d$-dimensional drawing such that there is a directed path from a vertex $u$ to a vertex $v$ in $G$ if $D(u) <D(v)$ for every dimension $D$ of $\Gamma$. We have a \emph{falsely implied path (fip)} when $D(u) < D(v)$ for every dimension $D$ of~$\Gamma$, but there is no path from $u$ to $v$. Minimizing the number of fips is an important theoretical and practical problem, which is NP-hard. We show that it is an FPT~problem for parameter $k$, where $k$ is the maximum degree of a vertex of the \emph{modular~decomposition~tree} of~$G$. Namely, for any constant $d$, we present an $O(nm+ndk^2(k!)^d)$ time algorithm to compute a weak $d$-dimensional dominance drawing $\Gamma$ of a DAG $G$ having the minimum number of fips. An interesting implication of this result is that we can decide if a DAG has dominance dimension~$3$ (a well-known NP-complete problem) in time $O(nm+nk^2(k!)^3)$.