206 research outputs found
Embedding Graphs into Embedded Graphs
Full text linkA (possibly degenerate) drawing of a graph G in the plane is approximable by an embedding if it can be turned into an embedding by an arbitrarily small perturbation.
We show that testing, whether a drawing of a planar graph G in the plane is approximable by an embedding, can be carried out in polynomial time, if a desired embedding of G belongs to a fixed isotopy class, i.e., the rotation system (or equivalently the faces) of the embedding of G and the choice of outer face are fixed.
In other words, we show that c-planarity with embedded pipes is tractable for graphs with fixed embeddings.
To the best of our knowledge an analogous result was previously known essentially only when G is a cycle
Hanani-Tutte for approximating maps of graphs
Full text linkWe resolve in the affirmative conjectures of Repovs and A. Skopenkov (1998),
and M. Skopenkov (2003) generalizing the classical Hanani-Tutte theorem to the
setting of approximating maps of graphs on 2-dimensional surfaces by
embeddings. Our proof of this result is constructive and almost immediately
implies an efficient algorithm for testing if a given piecewise linear map of a
graph in a surface is approximable by an embedding. More precisely, an instance
of this problem consists of (i) a graph G whose vertices are partitioned into
clusters and whose inter-cluster edges are partitioned into bundles, and (ii) a
region R of a 2-dimensional compact surface M given as the union of a set of
pairwise disjoint discs corresponding to the clusters and a set of pairwise
non-intersecting "pipes" corresponding to the bundles, connecting certain pairs
of these discs. We are to decide whether G can be embedded inside M so that the
vertices in every cluster are drawn in the corresponding disc, the edges in
every bundle pass only through its corresponding pipe, and every edge crosses
the boundary of each disc at most once.Comment: numerous correction
The Z_2-Genus of Kuratowski Minors
Full text linkA drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The Z_2-genus of a graph G is the minimum g such that G has an independently even drawing on the orientable surface of genus g. An unpublished result by Robertson and Seymour implies that for every t, every graph of sufficiently large genus contains as a minor a projective t x t grid or one of the following so-called t-Kuratowski graphs: K_{3,t}, or t copies of K_5 or K_{3,3} sharing at most 2 common vertices. We show that the Z_2-genus of graphs in these families is unbounded in t; in fact, equal to their genus. Together, this implies that the genus of a graph is bounded from above by a function of its Z_2-genus, solving a problem posed by Schaefer and Stefankovic, and giving an approximate version of the Hanani-Tutte theorem on orientable surfaces
Strong Hanani-Tutte for the Torus
Full text linkIf a graph can be drawn on the torus so that every two independent edges cross an even number of times, then the graph can be embedded on the torus
The Crossing Tverberg Theorem
Full text linkThe Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r, all share a common point. In this paper, we prove a strengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed.
As a concrete application, we show that any n points in the plane in general position span floor[n/3] vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing triangles. Our result generalizes to a result about simplices in R^d,d >=2
On the Page Number of Upward Planar Directed Acyclic Graphs
No full textIn this paper we study the page number of upward planar directed acyclic graphs. We prove that: (1) the page number of any n-vertex upward planar triangulation G whose every maximal 4-connected component has page number k is at most min{O(k log n), O(2k )}; (2) every upward planar triangulation G with o( n/log n) diameter has o(n) page number; and (3) every upward planar triangulation has a vertex ordering with o(n) page number if and only if every upward planar triangulation whose maximum degree is O(√n) does
Intersection patterns of edges in topological graphs
Full text linkThis thesis is devoted to crossing patterns of edges in topological graphs. We consider the following four problems: A thrackle is a graph drawn in the plane such that every pair of edges meet exactly once: either at a common endpoint or in a proper crossing. Conway's Thrackle Conjecture says that a thrackle cannot have more edges than vertices. By a computational approach we improve the previously known upper bound of 1.5n on the maximal number of edges in a thrackle with n vertices to 1.428n. Moreover, our method yields an algorithm with a finite running time that for any ε > 0 either verifies the upper bound of (1 + ε)n on the maximum number of edges in a thrackle or disproves the conjecture. It is not hard to see that any simple graph admits a poly-line drawing in the plane such that each edge is represented by a polygonal curve with at most three bends, and each edge crossings realizes a prescribed angle α. We show that if we restrict the number of bends per edge to two and allow edges to cross in k different angles, a graph on n vertices admitting such a drawing can have at most O(nk2) edges. This generalizes a previous result of Arikushi et al., in which the authors treated a special case of our problem, where k = 1 and the prescribed angle has 90 degrees. The classical result known as Hanani-Tutte Theorem states that a graph is planar if and only if it admits a drawing in the plane in which each pair of non-adjacent edges crosses an even number of times. We prove the following monotone variant of this result, conjectured by J.Pach and G.Tóth. If G has an x-monotone drawing in which every pair of independent edges crosses evenly, then G has an x-monotone embedding (i.e. a drawing without crossings) with the same vertex locations. We show several interesting algorithmic consequences of this result. In a drawing of a graph, two edges form an odd pair if they cross each other an odd number of times. A pair of edges is independent (or non-adjacent) if they share no endpoint. For a graph G we let ocr(G) be the smallest number of odd pairs in a drawing of G and let iocr(G) be the smallest number of independent odd pairs in a drawing of G. We construct a graph G with iocr(G) < ocr(G), answering a question by Székely, and –for the first time– giving evidence that crossings of adjacent edges may not always be trivial to eliminate.DC
Orthogeodesic Point-Set Embedding of Trees
Full text linkLet S be a set of N grid points in the plane, and let G a graph with n vertices (n ≤ N ). An orthogeodesic point-set embedding of G on S is a drawing of G such that each vertex is drawn as a point of S and each edge is an orthogonal chain with bends on grid points whose length is equal to the Manhattan distance.We study the following problem. Given a family of trees F what is the minimum value f (n) such that every n-vertex tree in F admits an orthogeodesic point-set embedding on every grid-point set of size f (n)? We provide polynomial upper bounds on f (n) for both planar and non-planar orthogeodesic point-set embeddings as well as for the case when edges are required to be L-shaped chains
Recognizing Weak Embeddings of Graphs
No full textWe present an efficient algorithm for a problem in the interface between clustering and graph embeddings. An embedding ' : G ! M of a graph G into a 2manifold M maps the vertices in V (G) to distinct points and the edges in E(G) to interior-disjoint Jordan arcs between the corresponding vertices. In applications in clustering, cartography, and visualization, nearby vertices and edges are often bundled to a common node or arc, due to data compression or low resolution. This raises the computational problem of deciding whether a given map ' : G ! M comes from an embedding. A map ' : G ! M is a weak embedding if it can be perturbed into an embedding ψ: G ! M with k' "k < " for every " > 0. A polynomial-time algorithm for recognizing weak embeddings was recently found by Fulek and Kyncl [14], which reduces to solving a system of linear equations over Z2. It runs in O(n2!) O(n4:75) time, where 2:373 is the matrix multiplication exponent and n is the number of vertices and edges of G. We improve the running time to O(n log n). Our algorithm is also conceptually simpler than [14]: We perform a sequence of local operations that gradually "untangles" the image '(G) into an embedding (G), or reports that ' is not a weak embedding. It generalizes a recent technique developed for the case that G is a cycle and the embedding is a simple polygon [1], and combines local constraints on the orientation of subgraphs directly, thereby eliminating the need for solving large systems of linear equations
C-Planarity of Embedded Cyclic c-Graphs
No full textWe show that c-planarity is solvable in quadratic time for flat clustered graphs with three clusters if the combinatorial embedding of the underlying graph is fixed. In simpler graph-theoretical terms our result can be viewed as follows. Given a graph G with the vertex set partitioned into three parts embedded on a 2-sphere, our algorithm decides if we can augment G by adding edges without creating an edge-crossing so that in the resulting spherical graph the vertices of each part induce a connected sub-graph. We proceed by a reduction to the problem of testing the existence of a perfect matching in planar bipartite graphs. We formulate our result in a slightly more general setting of cyclic clustered graphs, i.e., the simple graph obtained by contracting each cluster, where we disregard loops and multi-edges, is a cycle
- …
