Giuseppe Liotta

Steven Chaplick, Myroslav Kryven, Giuseppe Liotta et al.

We study straight-line drawings of graphs where the vertices are placed in convex position in the plane, i.e., \emph{convex drawings}. We consider two families of graph classes with convex drawings: \emph{outer $k$-planar} graphs, where each edge is crossed by at most $k$ other edges; and \emph{outer $k$-quasi-planar} graphs, where no $k$ edges can mutually cross. We show that the outer $k$-planar graphs are $\lfloor3.5\sqrt{k}\rfloor$-degenerate, and consequently that every outer $k$-planar graph can be colored with $\lfloor3.5\sqrt{k}\rfloor + 1$ colors. We further show that every outer $k$-planar graph has a balanced vertex separator of size at most $2k+3$. For each fixed $k$, these small balanced separators allow us to test outer $k$-planarity in quasi-polynomial time, e.g., this implies that none of these recognition problems is NP-hard unless the Exponential Time Hypothesis fails. We also show that the class of outer 3-quasi-planar graphs and the class of planar graphs are incomparable. Finally, we restrict outer $k$-planar and outer $k$-quasi-planar drawings to \emph{full} drawings (where no crossing appears on the boundary of the outer face) and to \emph{closed} drawings (where the vertex sequence on the boundary of the outer face is a Hamiltonian cycle in the graph). For each $k$, we express \emph{closed outer $k$-planarity} and \emph{closed outer $k$-quasi-planarity} in extended monadic second-order logic. Since every outer $k$-planar graph has treewidth $O(k)$, Courcelle's theorem implies that closed outer $k$-planarity is linear-time testable. We leverage this result to further show that full outer $k$-planarity can also be tested in linear time.

Stephen Kobourov, William Lenhart, Giuseppe Liotta et al.

We study the problem of simultaneous geometric embedding of two paths without self-intersections on an integer grid. We show that minimizing the length of the longest edge of such an embedding is NP-hard. We also show that we can minimize in $O(n^{3/2})$ time the perimeter of an integer grid containing such an embedding if one path is $x$-monotone and the other is $y$-monotone.

Wilhelm Kerle-Malcharek, Giulio Biondi, Karsten Klein et al.

Immersive technologies, such as virtual and augmented reality, are transforming digital heritage by enabling users to explore and interact with culturally significant sites. It is now possible to view and augment digital twins, or digitally reconstructed versions of them, and to enable access to previously unreachable locations for a broader audience. Here, we investigate retrieval-augmented generation (RAG)-based avatars as an interface for accessing further information about digital cultural heritage objects while immersed in dedicated virtual environments. We present a requirement design space that spans the application realm, avatar personality, and I/O modalities. We instantiate it with a RAG system coupled to a conversational avatar in a virtual reality (VR) environment, using the Maxentius mausoleum from the 4th century AD as a case study, through which users gain access to curated on-demand information of the digitised heritage object. Our workflow utilises scholarly texts and enriches them with metadata. We evaluate various RAG configurations in terms of answer quality on a small expert-crafted question-answer set, as well as the perceived workload of users of a VR setup using such a RAG avatar. We demonstrate evidence that users perceive the overall workload for interacting with such an avatar as below average and that such avatars help to gain topical engagement. Overall, our work demonstrates how to utilise RAG-driven VR avatars for archaeological purposes and provides evidence that they can offer a pathway for immersive, AI-enhanced digital heritage applications.

Todor Antić, Giuseppe Liotta, Tomáš Masařík et al.

Recently, there has been interest in representing single graphs by multiple drawings; for example, using graph stories, storyplans, or uncrossed collections. In this paper, we apply this idea to orthogonal graph drawing. Due to the orthogonal drawing style, we focus on 4-graphs, that is, graphs of maximum degree 4. We restrict ourselves to plane graphs, that is, planar graphs whose embedding is fixed. Our goal is to represent any plane 4-graph $G$ by an unbent collection, that is, a collection of orthogonal drawings of $G$ that adhere to the embedding of $G$ and ensure that each edge of $G$ is drawn without bends in at least one of the drawings. We investigate two objectives. First, we consider minimizing the number of drawings in an unbent collection. We prove that every plane 4-graph can be represented by a collection with at most three drawings, which is tight. We also give necessary and sufficient conditions for a graph to admit an unbent collection of size $2$. Second, we consider minimizing the total number of bends over all drawings in an unbent collection. We show that this problem is NP-hard and give a 3-approximation algorithm. For the special case of plane triconnected cubic graphs, we show how to compute minimum-bend collections in linear time.

Alessio Arleo, Walter Didimo, Giuseppe Liotta et al.

In social networks, individuals' decisions are strongly influenced by recommendations from their friends and acquaintances. The influence maximization (IM) problem asks to select a seed set of users that maximizes the influence spread, i.e., the expected number of users influenced through a stochastic diffusion process triggered by the seeds. In this paper, we present VAIM, a visual analytics system that supports users in analyzing the information diffusion process determined by different IM algorithms. By using VAIM one can: (i) simulate the information spread for a given seed set on a large network, (ii) analyze and compare the effectiveness of different seed sets, and (iii) modify the seed sets to improve the corresponding influence spread.