1,720,998 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
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
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
