From the 1 of 4 linked papers with an AI index.
4 papers
Extending Biconnected Straight-Line Planar Drawings
Giordano Andreola, Susanna Caroppo, Giordano Da Lozzo +5
The paper investigates the difficulty of extending a straight-line planar drawing of a biconnected subgraph to the whole graph, showing NP‑hardness in the variable‑embedding case a…
Quantum Time-Space Tradeoffs for Exponential Dynamic Programming
Susanna Caroppo, JevgÄnijs Vihrovs, Jevgēnijs Vihrovs +3
We investigate the quantum algorithms for dynamic programming by Ambainis et al. (SODA'19). While giving provable complexity speedups and applicable to a variety of NP-hard problem…
A Walk on the Wild Side: a Shape-First Methodology for Orthogonal Drawings
Giordano Andreola, Susanna Caroppo, Giuseppe Di Battista +3
Several algorithms for the construction of orthogonal drawings of graphs, including those based on the Topology-Shape-Metrics (TSM) paradigm, tend to prioritize the minimization of…
Upward Pointset Embeddings of Planar st-Graphs
Carlos Alegria, Susanna Caroppo, Giordano Da Lozzo +5
We study upward pointset embeddings (UPSEs) of planar -graphs. Let be a planar -graph and let be a pointset with . An UPSE of …