BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Walter Didimo

Walter Didimo contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsComputational GeometrySocial and Information NetworksDiscrete MathematicsHuman-Computer Interactionmath.CO

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
8works
0followers
6topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

8 published item(s)

preprint2022arXiv

Computing Bend-Minimum Orthogonal Drawings of Plane Series-Parallel Graphs in Linear Time

A planar orthogonal drawing of a planar 4-graph G (i.e., a planar graph with vertex-degree at most four) is a crossing-free drawing that maps each vertex of G to a distinct point of the plane and each edge of $G$ to a sequence of horizontal and vertical segments between its end-points. A longstanding open question in Graph Drawing, dating back over 30 years, is whether there exists a linear-time algorithm to compute an orthogonal drawing of a plane 4-graph with the minimum number of bends. The term "plane" indicates that the input graph comes together with a planar embedding, which must be preserved by the drawing (i.e., the drawing must have the same set of faces as the input graph). In this paper, we positively answer the question above for the widely-studied class of series-parallel graphs. Our linear-time algorithm is based on a characterization of the planar series-parallel graphs that admit an orthogonal drawing without bends. This characterization is given in terms of the orthogonal spirality that each type of triconnected component of the graph can take; the orthogonal spirality of a component measures how much that component is "rolled-up" in an orthogonal drawing of the graph.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Small Point-Sets Supporting Graph Stories

In a graph story the vertices enter a graph one at a time and each vertex persists in the graph for a fixed amount of time $ω$, called viewing window. At any time, the user can see only the drawing of the graph induced by the vertices in the viewing window and this determines a sequence of drawings. For readability, we require that all the drawings of the sequence are planar. For preserving the user's mental map we require that when a vertex or an edge is drawn, it has the same drawing for its entire life. We study the problem of drawing the entire sequence by mapping the vertices only to $ω+k$ given points, where $k$ is as small as possible. We show that: $(i)$ The problem does not depend on the specific set of points but only on its size; $(ii)$ the problem is NP-hard and is FPT when parameterized by $ω+k$; $(iii)$ there are families of graph stories that can be drawn with $k=0$ for any $ω$, while for $k=0$ and small values of $ω$ there are families of graph stories that can be drawn and others that cannot; $(iv)$ there are families of graph stories that cannot be drawn for any fixed $k$ and families of graph stories that require at least a certain $k$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

st-Orientations with Few Transitive Edges

The problem of orienting the edges of an undirected graph such that the resulting digraph is acyclic and has a single source s and a single sink t has a long tradition in graph theory and is central to many graph drawing algorithms. Such an orientation is called an st-orientation. We address the problem of computing st-orientations of undirected graphs with the minimum number of transitive edges. We prove that the problem is NP-hard in the general case. For planar graphs we describe an ILP model that is fast in practice. We experimentally show that optimum solutions dramatically reduce the number of transitive edges with respect to unconstrained st-orientations computed via classical st-numbering algorithms. Moreover, focusing on popular graph drawing algorithms that apply an st-orientation as a preliminary step, we show that reducing the number of transitive edges leads to drawings that are much more compact.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Rectilinear Planarity Testing of Plane Series-Parallel Graphs in Linear Time

A plane graph is rectilinear planar if it admits an embedding-preserving straight-line drawing where each edge is either horizontal or vertical. We prove that rectilinear planarity testing can be solved in optimal $O(n)$ time for any plane series-parallel graph $G$ with $n$ vertices. If $G$ is rectilinear planar, an embedding-preserving rectilinear planar drawing of $G$ can be constructed in $O(n)$ time. Our result is based on a characterization of rectilinear planar series-parallel graphs in terms of intervals of orthogonal spirality that their components can have, and it leads to an algorithm that can be easily implemented.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On Turn-Regular Orthogonal Representations

An interesting class of orthogonal representations consists of the so-called turn-regular ones, i.e., those that do not contain any pair of reflex corners that "point to each other" inside a face. For such a representation H it is possible to compute in linear time a minimum-area drawing, i.e., a drawing of minimum area over all possible assignments of vertex and bend coordinates of H. In contrast, finding a minimum-area drawing of H is NP-hard if H is non-turn-regular. This scenario naturally motivates the study of which graphs admit turn-regular orthogonal representations. In this paper we identify notable classes of biconnected planar graphs that always admit such representations, which can be computed in linear time. We also describe a linear-time testing algorithm for trees and provide a polynomial-time algorithm that tests whether a biconnected plane graph with "small" faces has a turn-regular orthogonal representation without bends.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Storyline Visualizations with Ubiquitous Actors

Storyline visualizations depict the temporal dynamics of social interactions, as they describe how groups of actors (individuals or organizations) change over time. A common constraint in storyline visualizations is that an actor cannot belong to two different groups at the same time instant. However, this constraint may be too severe in some application scenarios, thus we generalize the model by allowing an actor to simultaneously belong to distinct groups at any point in time. We call this model Storyline with Ubiquitous Actors (SUA). Essential to our model is that an actor is represented as a tree rather than a single line. We describe an algorithmic pipeline to compute storyline visualizations in the SUA model and discuss case studies on publication data.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

VAIM: Visual Analytics for Influence Maximization

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.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Simple $k$-Planar Graphs are Simple $(k+1)$-Quasiplanar

A simple topological graph is $k$-quasiplanar ($k\geq 2$) if it contains no $k$ pairwise crossing edges, and $k$-planar if no edge is crossed more than $k$ times. In this paper, we explore the relationship between $k$-planarity and $k$-quasiplanarity to show that, for $k \geq 2$, every $k$-planar simple topological graph can be transformed into a $(k+1)$-quasiplanar simple topological graph.

0 citations0 reviewsNo code linkedOpen access