Cologne Excellence Cluster on Cellular Stress Responses in Aging Associated Diseases
Graph Drawing E-print ArchiveNot a member yet
1225 research outputs found
Sort by
Obstacle Numbers of Planar Graphs.
No full textiven finitely many connected polygonal obstacles O1,…,Ok in the plane and a set P of points in general position and not in any obstacle, the visibility graph of P with obstacles O1,…,Ok
is the (geometric) graph with vertex set P, where two vertices are adjacent if the straight line segment joining them intersects no obstacle.
The obstacle number of a graph G is the smallest integer k such that G is the visibility graph of a set of points with k obstacles. If G is planar, we define the planar obstacle number of G by further requiring that the visibility graph has no crossing edges (hence that it is a planar geometric drawing of G).
In this paper, we prove that the maximum planar obstacle number of a planar graph of order n is n−3
, the maximum being attained (in particular) by maximal bipartite planar graphs.
This displays a significant difference with the standard obstacle number, as we prove that the obstacle number of every bipartite planar graph (and more generally in the class PURE-2-DIR of intersection graphs of straight line segments in two directions) of order at least 3 is 1
Many Touchings Force Many Crossings
No full textGiven n continuous open curves in the plane, we say that a pair is touching if they have only one interior point in common and at this point the first curve does not get from one side of the second curve to its other side. Otherwise, if the two curves intersect, they are said to form a crossing pair. Let t and c denote the number of touching pairs and crossing pairs, respectively. We prove that c≥1105t2n2, provided that t≥10n. Apart from the values of the constants, this result is best possible.
(Mathematical formula not displayed correctly!
Colored Point-Set Embeddings of Acyclic Graphs
No full textWe show that any planar drawing of a forest of three stars whose vertices are constrained to be at fixed vertex locations may require Ω(n23) edges each having Ω(n13)
bends in the worst case. The lower bound holds even when the function that maps vertices to points is not a bijection but it is defined by a 3-coloring. In contrast, a constant number of bends per edge can be obtained for 3-colored paths and for 3-colored caterpillars whose leaves all have the same color. Such results answer to a long standing open problem.
The work has been supported in part by the European project “Geospatial based Environment for Optimisation Systems Addressing Fire Emergencies” (GEO-SAFE), contract no. H2020-691161, by the Network Sciences and Technologies (NeST) initiative at University of Liverpool, and by the Italian project: “RISE: un nuovo framework distribuito per data collection, monitoraggio e comunicazioni in contesti di emergency response”, Fondazione Cassa Risparmio Perugia, code 2016.0104.021
Planar L-Drawings of Directed Graphs.
No full textWe study planar drawings of directed graphs in the L-drawing standard. We provide necessary conditions for the existence of these drawings and show that testing for the existence of a planar L-drawing is an NP-complete problem. Motivated by this result, we focus on upward-planar L-drawings. We show that directed st-graphs admitting an upward- (resp. upward-rightward-) planar L-drawing are exactly those admitting a bitonic (resp. monotonically increasing) st-ordering. We give a linear-time algorithm that computes a bitonic (resp. monotonically increasing) st-ordering of a planar st-graph or reports that there exists none
Flattening Polygonal Linkages via Uniform Angular Motion
No full textWe study the motion of polygonal linkages under the restriction that the angles between adjacent edges change uniformly to 0, π, or 2π. We show that convex polygons, orthogonally convex polygons and orthogonal 2-terraines unfold without self-intersection to a straight line in this model, but there exists an orthogonal 12-gon that does not. Further, we show that regular polygons, triangles, quadrilaterals, and convex pentagons can be reconfigured into flat zigzag chains; and every m x n rectangle made of unit-length edges can be reconfigured into a unit-length zigzag
On the Edge-Length Ratio of Outerplanar Graphs
No full textWe show that any outerplanar graph admits a planar straight-line drawing such that the length ratio of the longest to the shortest edges is strictly less than 2. This result is tight in the sense that for any ϵ>0 there are outerplanar graphs that cannot be drawn with an edge-length ratio smaller than 2−ϵ. We also show that every bipartite outerplanar graph has a planar straight-line drawing with edge-length ratio 1, and that, for any k≥1, there exists an outerplanar graph with a given combinatorial embedding such that any planar straight-line drawing has edge-length ratio greater than k
The Painter's Problem: Covering a Grid with Colored Connected Polygons.
No full textMotivated by a new way of visualizing hypergraphs, we study the following problem. Consider a rectangular grid and a set of colors χ. Each cell s in the grid is assigned a subset of colors χs⊆χ and should be partitioned such that for each color c∈χs at least one piece in the cell is identified with c. Cells assigned the empty color set remain white. We focus on the case where χ={red,blue}. Is it possible to partition each cell in the grid such that the unions of the resulting red and blue pieces form two connected polygons? We analyze the combinatorial properties and derive a necessary and sufficient condition for such a painting. We show that if a painting exists, there exists a painting with bounded complexity per cell. This painting has at most five colored pieces per cell if the grid contains white cells, and at most two colored pieces per cell if it does not
GiViP: A Visual Profiler for Distributed Graph Processing Systems
No full textAnalyzing large-scale graphs provides valuable insights in different application scenarios. While many graph processing systems working on top of distributed infrastructures have been proposed to deal with big graphs, the tasks of profiling and debugging their massive computations remain time consuming and error-prone. This paper presents GiViP, a visual profiler for distributed graph processing systems based on a Pregel-like computation model. GiViP captures the huge amount of messages exchanged throughout a computation and provides an interactive user interface for the visual analysis of the collected data. We show how to take advantage of GiViP to detect anomalies related to the computation and to the infrastructure, such as slow computing units and anomalous message patterns