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
Area, Curve Complexity, and Crossing Resolution of Non-planar Graph Drawings
No full textIn this paper we study non-planar drawings of graphs, and study tradeoffs between the crossing resolution (i.e., the minimum angle formed by two crossing segments), the curve complexity (i.e., maximum number of bends per edge), the total number of bends, and the area
On the Characterization of Level Planar Trees by Minimal Patterns
No full textWe consider characterizations of level planar trees. Healy et al. characterized the set of trees that are level planar in terms of two minimal level non-planar (MLNP) patterns. Fowler and Kobourov later proved that the set of patterns was incomplete and added two additional patterns. In this paper, we show that the characterization is still incomplete by providing new MLNP patterns not included in the previous characterizations. Moreover, we introduce an iterative method to create an arbitrary number of MLNP patterns, thus proving that the set of minimal patterns that characterizes level planar trees is infinite
Splitting Clusters to Get C-Planarity
No full textIn this paper we introduce a generalization of the c-planarity testing problem for clustered graphs. Namely, given a clustered graph, the goal of the S PLIT-C-P LANARITY problem is to split as few clusters as possible in order to make the graph c-planar. Determining whether zero splits are enough coincides with testing c-planarity. We show that S PLIT-C-P LANARITY is NP-complete for c-connected clustered triangulations and for non-c-connected clustered paths and cycles. On the other hand, we present a polynomial-time algorithm for flat c-connected clustered graphs whose underlying graph is a biconnected seriesparallel graph, both in the fixed and in the variable embedding setting, when the splits are assumed to maintain the c-connectivity of the clusters
Removing Independently Even Crossings
No full textWe show that cr(G) ≤ 2 iocr(G) settling an open problem of Pach and Tóth [5,1]. Moreover, iocr(G) = cr(G) if iocr(G) ≤ 2
The Art of Cheating When Drawing a Graph (Extended Abstract)
No full textThe prime directive of graph drawing is to depict a network faithfully and accurately. But sometimes it’s better to cheat. I will discuss a series of examples - both my own work and that of others - that involve discarding information, distorting the data, encouraging visual clutter, or even adding random noise. The benefits of breaking the rules can range from the scientific to the artistic
Geometric Simultaneous Embeddings of a Graph and a Matching
No full textThe geometric simultaneous embedding problem asks whether two planar graphs on the same set of vertices in the plane can be drawn using straight lines, such that each graph is plane. Geometric simultaneous embedding is a current topic in graph drawing and positive and negative results are known for various classes of graphs. So far only connected graphs have been considered. In this paper we present the first results for the setting where one of the graphs is a matching. In particular, we show that there exists a planar graph and a matching which do not admit a geometric simultaneous embedding. This generalizes the same result for a planar graph and a path. On the positive side, we describe algorithms that compute a geometric simultaneous embedding of a matching and a wheel, outerpath, or tree. Our proof for a matching and a tree sheds new light on a major open question: do a tree and a path always admit a geometric simultaneous embedding? Our drawing algorithms minimize the number of orientations used to draw the edges of the matching. Specifically, when embedding a matching and a tree, we can draw all matching edges horizontally. When embedding a matching and a wheel or an outerpath, we use only two orientations
Upward Planarization Layout
No full textRecently, we presented a new practical method for upward crossing minimization [6], which clearly outperformed existing approaches for drawing hierarchical graphs in that respect. The outcome of this method is an upward planar representation (UPR), a planarly embedded graph in which crossings are represented by dummy vertices. However, straight-forward approaches for drawing such UPRs lead to quite unsatisfactory results. In this paper, we present a new algorithm for drawing UPRs that greatly improves the layout quality, leading to good hierarchal drawings with few crossings. We analyze its performance on well-known benchmark graphs and compare it with alternative approaches
Drawing Hamiltonian Cycles with No Large Angles
No full textLet n ≥ 4 be even. It is shown that every set S of n points in the plane can be connected by a (possibly self-intersecting) spanning tour (Hamiltonian cycle) consisting of n straight line edges such that the angle between any two consecutive edges is at most 2π/3. For n = 4 and 6, this statement is tight. It is also shown that every even-element point set S can be partitioned into at most two subsets, S1 and S2 , each admitting a spanning tour with no angle larger than π/2. Fekete and Woeginger conjectured that for sufficiently large even n, every n-element set admits such a spanning tour. We confirm this conjecture for point sets in convex position. A much stronger result holds for large point sets randomly and uniformly selected from an open region bounded by finitely many rectifiable curves: for any ε > 0, these sets almost surely admit a spanning tour with no angle larger than ε
Algebraic Methods for Counting Euclidean Embeddings of Rigid Graphs
No full textThe study of (minimally) rigid graphs is motivated by numerous applications, mostly in robotics and bioinformatics. A major open problem concerns the number of embeddings of such graphs, up to rigid motions, in Euclidean space. We capture embeddability by polynomial systems with suitable structure, so that their mixed volume, which bounds the number of common roots, to yield interesting upper bounds on the number of embeddings. We focus on R2 and R3 , where Laman graphs and 1-skeleta of convex simplicial polyhedra, respectively, admit inductive Henneberg constructions. We establish the first general lower bound in R3 of about 2.52n , where n denotes the number of vertices. Moreover, our implementation yields upper bounds for n ≤ 10 in R2 and R3 , which reduce the existing gaps, and tight bounds up to n = 7 in R3 . Keywords: Rigid graph, Euclidean embedding, Henneberg construction, polynomial system, root bound, cyclohexane caterpillar