Source author record

Manuel Borrazzo

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms math.CO Discrete Mathematics

Catalog footprint

Research overview

2works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Drawing Graphs as Spanners

We study the problem of embedding graphs in the plane as good geometric spanners. That is, for a graph $G$ , the goal is to construct a straight-line drawing $Γ$ of $G$ in the plane such that, for any two vertices $u$ and $v$ of $G$ , the ratio between the minimum length of any path from $u$ to $v$ and the Euclidean distance between $u$ and $v$ is small. The maximum such ratio, over all pairs of vertices of $G$ , is the spanning ratio of $Γ$ . First, we show that deciding whether a graph admits a straight-line drawing with spanning ratio $1$ , a proper straight-line drawing with spanning ratio $1$ , and a planar straight-line drawing with spanning ratio $1$ are NP-complete, $\exists \mathbb R$ -complete, and linear-time solvable problems, respectively, where a drawing is proper if no two vertices overlap and no edge overlaps a vertex. Second, we show that moving from spanning ratio $1$ to spanning ratio $1+ε$ allows us to draw every graph. Namely, we prove that, for every $ε>0$ , every (planar) graph admits a proper (resp. planar) straight-line drawing with spanning ratio smaller than $1+ε$ . Third, our drawings with spanning ratio smaller than $1+ε$ have large edge-length ratio, that is, the ratio between the length of the longest edge and the length of the shortest edge is exponential. We show that this is sometimes unavoidable. More generally, we identify having bounded toughness as the criterion that distinguishes graphs that admit straight-line drawings with constant spanning ratio and polynomial edge-length ratio from graphs that require exponential edge-length ratio in any straight-line drawing with constant spanning ratio.

preprint2020arXiv

On the Planar Edge-Length Ratio of Planar Graphs

The edge-length ratio of a straight-line drawing of a graph is the ratio between the lengths of the longest and of the shortest edge in the drawing. The planar edge-length ratio of a planar graph is the minimum edge-length ratio of any planar straight-line drawing of the graph. In this paper, we study the planar edge-length ratio of planar graphs. We prove that there exist $n$ -vertex planar graphs whose planar edge-length ratio is in $Ω(n)$ ; this bound is tight. We also prove upper bounds on the planar edge-length ratio of several families of planar graphs, including series-parallel graphs and bipartite planar graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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