1,721,006 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
The -genus of Kuratowski minors
No full textA drawing of a graph on a surface is independently even if every pair of independent edges in the drawing crosses an even number of times.
The -genus of a graph is the minimum such that has an independently even drawing
on the orientable surface of genus . An unpublished result by Robertson and Seymour implies that for every , every graph of
sufficiently large genus contains as a minor a projective grid or one of the following so-called -Kuratowski
graphs: , or copies of or sharing at most common vertices. We show that the -genus
of graphs in these families is unbounded in ; in fact, equal to their genus. Together, this implies that the genus of a graph is
bounded from above by a function of its -genus, solving a problem posed by Schaefer and \v{S}tefankovi\v{c}, and
giving an approximate version of the Hanani-Tutte theorem on surfaces.
Joint work with J. Kyncl.Non UBCUnreviewedAuthor affiliation: IST AustriaPostdoctora
Recent Progress on the Hill's Conjecture
No full textNon UBCUnreviewedAuthor affiliation: Charles UniversityPostdoctora
Hanani-Tutte for approximating maps of graphs
No full textWe resolve in the affirmative conjectures of
A. Skopenkov and Repovs (1998), and M. Skopenkov (2003) generalizing the
classical Hanani--Tutte theorem to the setting of approximating maps of
graphs in the plane by embeddings. Our proof of this result is constructive,
and implies the existence of a polynomial-time algorithm for the following
problem.
An instance of the problem consists of (i) a graph whose vertices are
partitioned into clusters and whose inter-cluster edges are partitioned into
bundles, and (ii) a 2-dimensional surface given as the union of a set of
pairwise disjoint discs corresponding to the clusters and a set of pairwise
non-intersecting strips, ``pipes'', corresponding to the bundles, connecting
certain pairs of these discs.
We are to decide whether can be embedded inside 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.
Joint work with J. Kyncl.Non UBCUnreviewedAuthor affiliation: IST AustriaPostdoctora
Recommended from our members
Embedding Graphs into Embedded Graphs
No full textA (possibly degenerate) drawing of a graphGin 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 piece-wise linear drawing of a planar graphGin the plane is approximable by an embedding can be carried out in polynomial time, if a desired embedding ofGbelongs to a fixed isotopy class. In other words, we show that c-planarity with embedded pipes is tractable for graphs with prescribed combinatorial embedding. To the best of our knowledge, an analogous result was previously known essentially only whenGis a cycle.12 month embargo; published online: 11 June 2020This item from the UA Faculty Publications collection is made available by the University of Arizona with support from the University of Arizona Libraries. If you have questions, please contact us at [email protected]
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
Metric and analytic methods
No full textThe thesis deals with two separate problems. In the first part we show that the regular n×n grid of points in Z2 cannot be recovered from an arbitrary n2 -element subset of Z2 using only mappings with prescribed maximum stretch independent of n. This provides a negative answer to a question of Uriel Feige from 2002. The present approach builds on the work of Burago and Kleiner and McMullen from 1998 on bilipschitz non-realisable densities and bilipschitz non-equivalence of separated nets in the plane. We describe a procedure that takes a positive, measurable function and encodes it into a sequence of discrete sets. Then we show that applying this procedure to a typical positive, continuous function on the unit square yields a counter-example to Feige's question. Along the way we provide a new proof of a result on bilipschitz decomposition for Lipschitz regular mappings, which was originally proved by Bonk and Kleiner in 2002. In the second part we provide a constructive proof for the strong Hanani- Tutte theorem on the projective plane. In contrast to the previous proof by Pelsmajer, Schaefer and Stasi from 2009, the presented approach does not rely on characterisation of embeddability into the projective plane via forbidden minors.
- …
