The Wiener index of a graph G, denoted by W(G), is the sum of all distances between pairs of vertices in G. Originally called the path number and used to predict the boiling points of paraffin ...molecules, W(G) has been studied extensively from both a chemical perspective and a mathematical perspective. In this article, we consider a completely unexplored aspect of the Wiener index involving a cellularly embedded graph and its dual graph. For a cellularly embedded graph G on a given surface S and its dual graph G⁎, we define the Wiener ratio of G on S, denoted by Λ(G), as the minimum value between W(G)/W(G⁎) and W(G⁎)/W(G). We elucidate some basic properties of Λ(G), explore convergence of the Wiener ratios of families of cellularly embedded graphs and prove a density result, and then conclude with some open questions about the Wiener ratio.
(Meta) Kernelization Bodlaender, Hans L; Fomin, Fedor V; Lokshtanov, Daniel ...
Journal of the ACM,
12/2016, Letnik:
63, Številka:
5
Journal Article
Recenzirano
Odprti dostop
In a parameterized problem, every instance I comes with a positive integer k. The problem is said to admit a polynomial kernel if, in polynomial time, one can reduce the size of the instance I to a ...polynomial in k while preserving the answer. In this work, we give two meta-theorems on kernelization. The first theorem says that all problems expressible in counting monadic second-order logic and satisfying a coverability property admit a polynomial kernel on graphs of bounded genus. Our second result is that all problems that have finite integer index and satisfy a weaker coverability property admit a linear kernel on graphs of bounded genus. These theorems unify and extend all previously known kernelization results for planar graph problems.
Distance measures for embedded graphs Akitaya, Hugo A.; Buchin, Maike; Kilgus, Bernhard ...
Computational geometry : theory and applications,
April 2021, 2021-04-00, Letnik:
95
Journal Article
Recenzirano
Odprti dostop
We introduce new distance measures for comparing straight-line embedded graphs based on the Fréchet distance and the weak Fréchet distance. These graph distances are defined using continuous mappings ...and thus take the combinatorial structure as well as the geometric embeddings of the graphs into account. We present a general algorithmic approach for computing these graph distances. Although we show that deciding the distances is NP-hard for general embedded graphs, we prove that our approach yields polynomial time algorithms if the graphs are trees, and for the distance based on the weak Fréchet distance if the graphs are planar embedded and if the embedding meets a certain geometric restriction. Moreover, we prove that deciding the distances based on the Fréchet distance remains NP-hard for planar embedded graphs and show how our general algorithmic approach yields an exponential time algorithm and a polynomial time approximation algorithm for this case.
A Tutte polynomial for non-orientable maps Goodall, Andrew; Litjens, Bart; Regts, Guus ...
Electronic notes in discrete mathematics,
August 2017, 2017-08-00, Letnik:
61
Journal Article
We construct a new polynomial invariant of maps (graphs embedded in closed surfaces, not necessarily orientable). Our invariant is tailored to contain as evaluations the number of local flows and ...local tensions taking non-identity values in any given finite group. Moreover, it contains as specializations the Krushkal polynomial, the Bollobás-Riordan polynomial, the Las Vergnas polynomial, and their extensions to non-orientable surfaces, and hence in particular the Tutte polynomial of the under-lying graph of the map.
Stanley's symmetrized chromatic polynomial is a generalization of the ordinary chromatic polynomial to a graph invariant with values in a ring of polynomials in infinitely many variables. The ...ordinary chromatic polynomial is a specialization of Stanley's one.
To each orientable embedded graph with a single vertex, a simple graph is associated, which is called the intersection graph of the embedded graph. As a result, we can define Stanley's symmetrized chromatic polynomial for any orientable embedded graph with a single vertex. Our goal is to extend Stanley's chromatic polynomial to embedded graphs with arbitrary number of vertices, and not necessarily orientable. In contrast to well-known extensions of, say, the Tutte polynomial from abstract to embedded graphs 4, our extension is based not on the structure of the underlying abstract graph and the additional information about the embedding. Instead, we consider the binary delta-matroid associated to an embedded graph and define the extended Stanley chromatic polynomial as an invariant of binary delta-matroids. We show that, similarly to Stanley's symmetrized chromatic polynomial of graphs, which satisfies 4-term relations for simple graphs, the polynomial that we introduce satisfies the 4-term relations for binary delta-matroids 7.
For graphs, Stanley's chromatic function produces a knot invariant by means of the correspondence between simple graphs and knots. Analogously we may interpret the suggested extension as an invariant of links, using the correspondence between binary delta-matroids and links.
We investigate a class of growing graphs embedded into the
d
-dimensional torus where new vertices arrive according to a Poisson process in time, are randomly placed in space and connect to existing ...vertices with a probability depending on time, their spatial distance and their relative birth times. This simple model for a scale-free network is called the
age-based spatial preferential attachment network
and is based on the idea of preferential attachment with spatially induced clustering. We show that the graphs converge weakly locally to a variant of the random connection model, which we call the
age-dependent random connection model
. This is a natural infinite graph on a Poisson point process where points are marked by a uniformly distributed age and connected with a probability depending on their spatial distance and both ages. We use the limiting structure to investigate asymptotic degree distribution, clustering coefficients and typical edge lengths in the age-based spatial preferential attachment network.
In this paper we introduce and study the
strip planarity testing
problem, which takes as an input a planar graph
G
(
V
,
E
) and a function
γ
:
V
→
{
1
,
2
,
⋯
,
k
}
and asks whether a planar ...drawing of
G
exists such that each edge is represented by a curve that is monotone in the
y
-direction and, for any
u
,
v
∈
V
with
γ
(
u
)
<
γ
(
v
)
, it holds that
y
(
u
)
<
y
(
v
)
. The problem has strong relationships with some of the most deeply studied variants of the planarity testing problem, such as
clustered planarity
,
upward planarity
, and
level planarity
. Most notably, we provide a polynomial-time reduction from strip planarity testing to clustered planarity. We show that the strip planarity testing problem is polynomial-time solvable if
G
has a prescribed combinatorial embedding.
PDF
