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
Maximum Planar Subgraphs and Nice Embeddings: Practical Layout Tools
No full textIn automatic graph drawing a given graph has to be layed-out in the plane, usually according to a number of topological and aesthetic constraints. Nice drawings for sparse nonplanar graphs can be achieved by determining a maximum planar subgraph and augmenting an embedding of this graph. This approach appears to be of limited value in practice, because the maximum planar subgraph problem is NP-hard.
We attack the maximum planar subgraph problem with a branch-and-cut technique which gives us quite good and in many cases provably optimum solutions for sparse graphs and very dense graphs. In the theoretical part of the paper, the polytope of all planar subgraphs of a graph G is defined and studied. All subgraphs of a graph G, which are subdivisions of K5 or K3,3, turn out to define facets of this polytope. For cliques contained in G, the Euler inequalities turn out to be facet-defining for the planar subgraph polytope. Moreover we introduce the subdivision inequalities, V2k inequalities and flower inequalities all of which are facet-defining for the polytope. Furthermore, the composition of inequalities by 2-sums is investigated.
We also present computational experience with a branch-and-cut algorithm for the above problem. Our approach is based on an algorithm which searches for forbidden substructures in a graph that contains a subdivision of K5 or K3,3. These structures give us inequalities which are used as cutting planes.
Finally, we try to convince the reader that the computation of maximum planar subgraphs is indeed a practical tool for finding nice embeddings by applying this method to graphs taken from the literature
Representation of planar graphs by segments
No full textGiven any bipartite planar graph G, one can assign vertical and horizontal segments to its vertices so that (a) no two of them have an interior point in common, (b) two segments have a point in common if and only if the corresponding vertices are adjacent in G
Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition
No full textA geometric graph is angle-monotone if every pair of vertices has a path between them that—after some rotation—is x- and y-monotone. Angle-monotone graphs are √2-spanners and they are increasing-chord graphs. Dehkordi, Frati, and Gudmundsson introduced angle-monotone graphs in 2014 and proved that Gabriel triangulations are angle-monotone graphs. We give a polynomial time algorithm to recognize angle-monotone geometric graphs. We prove that every point set has a plane geometric graph that is generalized angle-monotone—specifically, we prove that the half-θ6-graph is generalized angle-monotone. We give a local routing algorithm for Gabriel triangulations that finds a path from any vertex s to any vertex t whose length is within 1+√2 times the Euclidean distance from s to t. Finally, we prove some lower bounds and limits on local routing algorithms on Gabriel triangulations
Grid-Obstacle Representations with Connections to Staircase Guarding
No full textIn this paper, we study grid-obstacle representations of graphs where we assign grid-points to vertices and define obstacles such that an edge exists if and only if an xy-monotone grid path connects the two endpoints without hitting an obstacle or another vertex. It was previously argued that all planar graphs have a grid-obstacle representation in 2D, and all graphs have a grid-obstacle representation in 3D. In this paper, we show that such constructions are possible with significantly smaller grid-size than previously achieved. Then we study the variant where vertices are not blocking, and show that then grid-obstacle representations exist for bipartite graphs. The latter has applications in so-called staircase guarding of orthogonal polygons; using our grid-obstacle representations, we show that staircase guarding is NP-hard in 2D
The Bundled Crossing Number
No full textWe study the algorithmic aspect of edge bundling. A bundled crossing in a drawing of a graph is a group of crossings between two sets of parallel edges. The bundled crossing number is the minimum number of bundled crossings that group all crossings in a drawing of the graph.
We show that the bundled crossing number is closely related to the orientable genus of the graph. If multiple crossings and self-intersections of edges are allowed, the two values are identical; otherwise, the bundled crossing number can be higher than the genus.
We then investigate the problem of minimizing the number of bundled crossings. For circular graph layouts with a fixed order of vertices, we present a constant-factor approximation algorithm. When the circular order is not prescribed, we get a 6c/c−2
-approximation for a graph with n vertices having at least cn edges for c>2. For general graph layouts, we develop an algorithm with an approximation factor of 6c/c−3 for graphs with at least cn edges for c>3