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
Bounded-Degree Graphs have Arbitrarily Large Geometric Thickness
Get PDFThe geometric thickness of a graph G is the minimum integer k such that there is a straight line drawing of G with its edge set partitioned into k plane subgraphs. Eppstein [Separating thickness from geometric thickness. In Towards a Theory of Geometric Graphs, vol. 342 of Contemp. Math., AMS, 2004] asked whether every graph of bounded maximum degree has bounded geometric thickness. We answer this question in the negative, by proving that there exists -regular graphs with arbitrarily large geometric thickness. In particular, for all and for all large n, there exists a -regular graph with geometric thickness at least . Analogous results concerning graph drawings with few edge slopes are also presented, thus solving open problems by Dujmovi{\'c} et~al.\ [Really straight graph drawings. In Proc. 12th International Symp. on Graph Drawing (GD '04), vol. 3383 of Lecture Notes in Comput. Sci., Springer, 2004] and Ambrus et~al.\ [The slope parameter of graphs. Tech. Rep. MAT-2005-07, Department of Mathematics, Technical University of Denmark, 2005]
Drawing Planar Bipartite Graphs With Small Area
No full textIn this paper, we study planar straight-line drawings of
bipartite planar graphs. We show that these graphs admit
drawings in an n/2 x (n/2-1) -grid, and that this is optimal.
Our results generalize to triangle-free planar graphs
Crossing Minimization for Symmetries
No full textWe consider the problem of drawing a graph with a given symmetry such that the number of edge crossings is minimal. We show that this problem is NP-hard, even if the order of orbits around the rotation center or along the reflection axis is fixed. We devise an algorithm for computing a crossing minimal drawing if inter-orbit edges may not cross orbits, showing in particular that intra-orbit edges do not contribute to the NP-hardness of the crossing minimization problem for symmetries
Drawing Pfaffian Graphs
No full textWe prove that a graph is Pfaffian if and only if it can be drawn in the plane (possibly with crossings) so that every perfect matching intersects itself an even number of times
New Theoretical Bounds of Visibility Representation of Plane Graphs
No full textIn a visibility representation (VR for short) of a plane graph G, each vertex of G is represented by a horizontal line segment such that the line segments representing any two adjacent vertices of G are joined by a vertical line segment. Rosenstiehl and Tarjan [6], Tamassia and Tollis [7] independently gave linear time VR algorithms for 2-connected plane graph. Afterwards, one of the main concerns for VR is the size of VR. In this paper, we prove that any plane graph G has a VR with height bounded by . This improves the previously known bound . We also construct a plane graph G with n vertices where any VR of G require a size of . Our result provides an answer to Kantrsquos open question about whether there exists a plane graph G such that all of its VR require width greater that cn, where c > 1.
Research supported in part by NSF Grant CCR-0309953
Open Problems Wiki
No full textThis project was inspired by the last year's paper on Selected Open Problems in Graph Drawing by Brandenburg et al. (Proc. 11th GD. Vol. 2919 of LNCS. (2003) 515–539). While being a very good start, a paper is inherently static and will become out-dated. For dynamic content, what open problems (hopefully) are, a web-site is more appropriate. Keeping such a site up-to-date, however, is time consuming and requires good knowledge of recent work. In projects like the free encyclopedia Wikipedia these obstacles are overcome with a collaborative approach: everyone is allowed, and even requested, to contribute his knowledge to the site. The Open Problems Wiki makes use of this paradigm to provide a forum for collecting open problems in graph drawing
Two Results on Intersection Graphs of Polygons
No full textIntersection graphs of convex polygons inscribed to a circle, so called polygon-circle graphs, generalize several well studied classes of graphs, e.g., interval graphs, circle graphs, circular-arc graphs and chordal graphs. We consider the question how complicated need to be the polygons in a polygon-circle representation of a graph.
Let cmp(n) denote the minimum k such that every polygon-circle graph on n vertices is the intersection graph of k-gons inscribed to the circle. We prove that cmp(n) = n-log_{2}n + o(log_{2}n) by showing that for every positive constant c < 1, cmp(n) \le n - c log n for every sufficiently large n, and by providing an explicit construction of polygon-circle graphs on n vertices which are not representable by polygons with less than n-logn-2loglogn corners. We also show that recognizing intersection graphs of k-gons inscribed in a circle is an NP-complete problem for every fixed k \ge 3
Stretching of Jordan Arc Contact Systems
No full textWe prove that a contact system of Jordan arcs is stretchable if and only if it is extendable into a weak arrangement of pseudo-lines
An Integer Programming Approach to Fuzzy Symmetry Detection
No full textThe problem of exact symmetry detection in general graphs has received much attention recently. In spite of its NP-hardness, two different algorithms have been presented that in general can solve this problem quickly in practice [5,2]. However, as most graphs do not admit any exact symmetry at all, the much harder problem of fuzzy symmetry detection arises: a minimal number of certain modifications of the graph should be allowed in order to make it symmetric. We present a general approach to this problem: we allow arbitrary edge deletions and edge creations; every single modification can be given an individual weight. We apply integer programming techniques to solve this problem exactly or heuristically and give runtime results for a first implementation
Convex Drawing for c-Planar Biconnected Clustered Graphs
No full textIn a graph, a cluster is a set of vertices, and two clusters are said to be non-intersecting if they are disjoint or one of them is contained in the other. A clustered graph is a graph with a set of non-intersecting clusters. In this paper, we assume that the graph is planar, each non leaf cluster has exactly two child clusters in the tree representation of non-intersecting clusters, and each cluster induces a biconnected subgraph. Then we show that such a clustered graph admits a drawing in the plane such that (i) edges are drawn as straight line segments with no crossing between two edges, and (ii) the boundary of the biconnected subgraph induced by each cluster is convex polygon