5 papers
How Close is a Tree to a Euclidean Minimum Spanning Tree?
Todor AntiÄ, JiÅà Fiala, Jelena GliÅ¡iÄ +8
Let be a straight-line crossing-free drawing of a tree . A \emph{bad pair} in is a pair of non-adjacent vertices of whose Euclidean distance in is smaller tha…
Beyond Outerplanarity
Steven Chaplick, Myroslav Kryven, Giuseppe Liotta +2
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 wit…
Parameterized Approaches to Orthogonal Compaction
Walter Didimo, Siddharth Gupta, Philipp Kindermann +3
Orthogonal graph drawings are used in applications such as UML diagrams, VLSI layout, cable plans, and metro maps. We focus on drawing planar graphs and assume that we are given an…
Three Edge-disjoint Plane Spanning Paths in a Point Set
Philipp Kindermann, Jan KratochvÃl, Giuseppe Liotta +1
We consider the following problem: Given a set of distinct points in the plane, how many edge-disjoint plane straight-line spanning paths can be drawn on ? Each spanning…
Optimal Orthogonal Drawings in Linear Time
Walter Didimo, Giuseppe Liotta, Giacomo Ortali +1
A planar orthogonal drawing Î of a connected planar graph G is a geometric representation of G such that the vertices are drawn as distinct points of the plane, the edges are draw…