2 citations · 5 across the 14 of their papers we have counts for
12 papers · 1 filter
On the Parameterized Complexity of Computing -Orientations with Few Transitive Edges
Carla Binucci, Giuseppe Liotta, Fabrizio Montecchiani +2
Orienting the edges of an undirected graph such that the resulting digraph satisfies some given constraints is a classical problem in graph theory, with multiple algorithmic applic…
Spirality and Rectilinear Planarity Testing of Independent-Parallel SP-Graphs
Walter Didimo, Michael Kaufmann, Giuseppe Liotta +1
We study the long-standing open problem of efficiently testing rectilinear planarity of series-parallel graphs (SP-graphs) in the variable embedding setting. A key ingredient behin…
Rectilinear Planarity Testing of Plane Series-Parallel Graphs in Linear Time
Walter Didimo, Michael Kaufmann, Giuseppe Liotta +1
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…
Optimal Orthogonal Drawings of Planar 3-Graphs in Linear Time
Walter Didimo, Giuseppe Liotta, Giacomo Ortali +1
A planar orthogonal drawing of a planar graph is a geometric representation of such that the vertices are drawn as distinct points of the plane, the edges are drawn as…
Simultaneous FPQ-Ordering and Hybrid Planarity Testing
Giuseppe Liotta, Ignaz Rutter, Alessandra Tappini
We study the interplay between embedding constrained planarity and hybrid planarity testing. We consider a constrained planarity testing problem, called 1-Fixed Constrained Planari…
The QuaSEFE Problem
Patrizio Angelini, Henry Förster, Michael Hoffmann +4
We initiate the study of Simultaneous Graph Embedding with Fixed Edges in the beyond planarity framework. In the QuaSEFE problem, we allow edge crossings, as long as each graph ind…