Search

The middle graph M(G) of a graph G is an intersection graph on the vertex set V (G) of any graph G. Let E(G) be an edge set of G and F = V 0(G) [ E(G), where V 0(G) indicates the family of all one vertex subsets of the set V (G). This concept was introduced by T. Hamada and I. Yoshimura [4]. M. Chandramouleeswaran et al., studied isomorphism and automorphism groups for semiring valued graph (S-valued graph). In this paper, we study the morphisms and its properties of middle graph of S-valued graphs. [ABSTRACT FROM AUTHOR]

Let H = 〈 V , S 〉 be a hypergraph, where V is a set of vertices and S is a set of clusters S 1 , ... , S m , S i ⊆ V , such that the clusters in S are not necessarily disjoint. This paper considers the Clustered Spanning Tree by Paths problem, denoted by CSTP. This problem aims to decide whether a feasible solution tree exists, spanning all vertices of V , such that each cluster induces a path in the solution tree. We introduce the idea of a minimum cardinality feasible removal list and a minimum cardinality feasible insertion list, which removes or inserts vertices from or into clusters, such that using each one of the lists separately creates hypergraphs with feasible solution trees for CSTP. In addition, we decompose the intersection graph of H into smaller instances, for those cases where the intersection graph contains a cut node or a separating edge. We demonstrate how to compose a minimum cardinality feasible removal list or a minimum cardinality feasible insertion list of a given hypergraph from the smaller minimum cardinality feasible removal lists or minimum cardinality feasible insertion lists of the smaller instances. This approach may reduce the size and intricacy of the instances. [ABSTRACT FROM AUTHOR]

We show how to solve a maximum clique problem on a given graph by an equivalent problem on an auxiliary graph. The transformation has interesting consequences in the bilevel setting. In fact, it allows to map a clique interdiction problem with edge interdiction into a clique interdiction problem with node interdiction. As a byproduct of the mapping, we can generalize to the edge interdiction problem complexity and algorithmic results that hold for the node interdiction problem. [ABSTRACT FROM AUTHOR]

Heterogeneous graph embedding models based on non-contrastive learning (NCL) do not rely on negative sampling to learn the intrinsic features and patterns, which may cause the model fail to efficiently learn the differences between vertexes. This paper proposed a heterogeneous graph embedding model based on cross-view prototype non-contrastive learning (XPNCL), which learnt better node representations for downstream tasks by finding additional positive samples with more contextual information, and reconsidered the similarity between positive samples. The model firstly designed a tree structure based on random walks in heterogeneous graph. This directed filtering tree (DFT) about positive samples contained rich neighboring and semantic information by filtering out random walk paths that satisfied local structural constraints. Secondly, to achieve the alignment of similar samples in terms of numerical and quantitative from multiple dimensions, XP-NCL defined the cross-view prototype index (ISDR) and peak operator based on the characteristics of heterogeneous graphs. Furthermore, the model trained using stop-gradient updating. Finally, experiments verify the classification and clustering performance of the node on ACM, DBLP and freebase datasets, and the results show that even without the negative samples, the XP-NCL representation can achieve superior performance in many cases compared to other homogeneous and heterogeneous graph baselines. [ABSTRACT FROM AUTHOR]

Chordal graphs are the intersection graphs of subtrees of a tree, while interval graphs of subpaths of a path. Undirected path graphs, directed path graphs and rooted directed path graphs are intermediate graph classes, defined, respectively, as the intersection graphs of paths of a tree, of directed paths of an oriented tree, and of directed paths of an out branching. All of these path graphs have vertex leafage 2. DominatingSet, ConnectedDominatingSet, and Steinertree problems are W[2]$$ \mathrm{W}\left[2\right] $$‐hard parameterized by the size of the solution on chordal graphs, NP$$ \mathrm{NP} $$‐complete on undirected path graphs, and polynomial‐time solvable on rooted directed path graphs, and hence also on interval graphs. We further investigate the (parameterized) complexity of all these problems when constrained to chordal graphs, taking the vertex leafage and the aforementioned classes into consideration. We prove that DominatingSet, ConnectedDominatingSet, and Steinertree are FPT$$ \mathrm{FPT} $$ on chordal graphs when parameterized by the size of the solution plus the vertex leafage, and that WeightedConnectedDominatingSet is polynomial‐time solvable on strongly chordal graphs. We also introduce a new subclass of undirected path graphs, which we call in–out rooted directed path graphs, as the intersection graphs of directed paths of an in–out branching. We prove that DominatingSet, ConnectedDominatingSet, and Steinertree are solvable in polynomial time on this class, generalizing the polynomiality for rooted directed path graphs proved by Booth and Johnson (SIAM J. Comput. 11 (1982), 191‐199.) and by White et al. (Networks 15 (1985), 109‐124.). [ABSTRACT FROM AUTHOR]

Multiple interval graphs are a well-known generalization of interval graphs introduced in the 1970s to deal with situations arising naturally in scheduling and allocation. A d -interval is the union of d disjoint intervals on the real line, and a graph is a d -interval graph if it is the intersection graph of d -intervals. In particular, it is a unit d -interval graph if it admits a d -interval representation where every interval has unit length. Whereas it has been known for a long time that recognizing 2-interval graphs and other related classes such as 2-track interval graphs is NP -complete, the complexity of recognizing unit 2-interval graphs remains open. Here, we settle this question by proving that the recognition of unit 2-interval graphs is also NP -complete. Our proof technique uses a completely different approach from the other hardness results of recognizing related classes. Furthermore, we extend the result for unit d -interval graphs for any d ≥ 2 , which does not follow directly in graph recognition problems — as an example, it took almost 20 years to close the gap between d = 2 and d > 2 for the recognition of d -track interval graphs. Our result has several implications, including that for every d ≥ 2 , recognizing (x , ... , x) d -interval graphs and depth r unit d -interval graphs is NP -complete for every x ≥ 11 and every r ≥ 4. [ABSTRACT FROM AUTHOR]

Let $\mathcal{V}$ and $\mathcal{U}$ be the point sets of two independent homogeneous Poisson processes on $\mathbb{R}^d$. A graph $\mathcal{G}_\mathcal{V}$ with vertex set $\mathcal{V}$ is constructed by first connecting pairs of points (v , u) with $v\in\mathcal{V}$ and $u\in\mathcal{U}$ independently with probability $g(v-u)$ , where g is a non-increasing radial function, and then connecting two points $v_1,v_2\in\mathcal{V}$ if and only if they have a joint neighbor $u\in\mathcal{U}$. This gives rise to a random intersection graph on $\mathbb{R}^d$. Local properties of the graph, including the degree distribution, are investigated and quantified in terms of the intensities of the underlying Poisson processes and the function g. Furthermore, the percolation properties of the graph are characterized and shown to differ depending on whether g has bounded or unbounded support. [ABSTRACT FROM AUTHOR]

In this paper, we examine the intersection of two previously recognised dimensions of students’ interpretations of symbolic notations within graphs of functions. One dimension distinguishes location-thinking, where notations refer only to a point’s location on a graph, from value-thinking, where such a point is treated as a multiplicative object. The other dimension distinguishes a nominal interpretation of expressions, where expressions refer to positions in the plane, from cardinal and magnitude interpretations, where expressions describe a discrete count of units, or measure of length, respectively. Taken together these dimensions provide six distinct ways students interpret expressions, especially those involving function notation, on graphs. Further, the frameworks offer suggestions about the ways of thinking underlying each interpretation. Each case reveals new meanings and affordances indicated by the interplay between the two dimensions. We provide both a theoretical account and empirical example of each case. [ABSTRACT FROM AUTHOR]

The clique transversal problem is a critical concept in graph theory, focused on identifying a minimum subset of vertices that intersects all maximal cliques in a graph. This problem and its variations—such as the k-fold clique, { k } -clique, minus clique, and signed clique transversal problems—have received significant interest due to their theoretical importance and practical applications. This paper examines the k-fold clique, { k } -clique, minus clique, and signed clique transversal problems on distance-hereditary graphs. Known for their distinctive structural properties, distance hereditary graphs provide an ideal framework for studying these problem variants. By exploring these issues in the context of distance-hereditary graphs, this research enhances the understanding of the computational challenges and the potential for developing efficient algorithms to address these problems. [ABSTRACT FROM AUTHOR]

Understanding the intricate architecture of the brain through the lens of graph theory and advanced neuroimaging techniques has become increasingly pivotal in unraveling the complexities of neural networks. This bibliometric analysis explores the evolving landscape of brain research by focusing on the intersection of graph theoretical approaches, neuroanatomy, and diverse neuroimaging modalities. A systematic search strategy was used that resulted in the retrieval of a comprehensive dataset of articles and reviews. Using CiteSpace and VOSviewer, a detailed scientometric analysis was conducted that revealed emerging trends, key research clusters, and influential contributions within this multidisciplinary domain. Our review highlights the growing synergy between graph theory methodologies and neuroimaging modalities, reflecting the evolving paradigms shaping our understanding of brain networks. This study offers comprehensive insight into brain network research, emphasizing growth patterns, pivotal contributions, and global collaborative networks, thus serving as a valuable resource for researchers and institutions navigating this interdisciplinary landscape. [ABSTRACT FROM AUTHOR]

The Maximum Independent Set problem is well-studied in graph theory and related areas. An independent set of a graph is a subset of non-adjacent vertices of the graph. A maximum independent set is an independent set of maximum size. This paper studies the Maximum Independent Set problem in some classes of geometric intersection graphs in a distributed setting. More precisely, we study the Maximum Independent Set problem on two geometric intersection graphs, interval and axis-parallel segment intersection graphs, and present deterministic distributed algorithms in a model that is similar but a little weaker than the local communication model. We compute the maximum independent set on interval graphs in O(k) rounds and O(n) messages, where k is the size of the maximum independent set and n is the number of nodes in the graph. We provide a matching lower bound of Ω(k) on the number of rounds, whereas Ω(n) is a trivial lower bound on message complexity. Thus, our algorithm is both time and message-optimal. We also study the Maximum Independent Set problem in interval count l graphs, a special case of the interval graphs where the intervals have exactly l different lengths. We propose an 1 2-approximation algorithm that runs in O(l) round. For axis-parallel segment intersection graphs, we design an 1 2-approximation algorithm that obtains a solution in O(D) rounds. The results in this paper extend the results of Molla et al. [J. Parallel Distrib. Comput. 2019]. [ABSTRACT FROM AUTHOR]

The problem of intersection graphs was introduced by Szpilrajn-Marczewski in 1945. This study introduces a new variant of the intersection graph, called the k-restricted intersection graph. Let Sn be a nonempty n-element set, for some positive integer n, and let S(n,k) be the set of all the k-element subsets of Sn where 0 ≤ k ≤ n. A k-restricted intersection graph, denoted by GS(n,k), is a graph with vertex set S(n,k) such that two vertices A, B ∈ S(n,k) are adjacent whenever A ∩ B ̸= ∅ and A ̸= B. Here, we determined the order and size of GS(n,k) . Moreover, some parameters such as independence number, domination number, and isolate domination number of the k-restricted intersection graph were established. Finally, necessary and sufficient conditions for a GS(n,k) to be isomorphic to the cycle graph and complete graph were determined. [ABSTRACT FROM AUTHOR]

The hull of a linear code is defined to be the intersection of the code and its dual, and was originally introduced to classify finite projective planes. The objective of this paper is to construct some MDS codes with l-Galois hulls of arbitrary dimensions by using the generalized Reed–Solomon codes over finite fields with regard to l-Galois inner product. We give a general construction theorem and some construction ideas of MDS with l-Galois hulls of arbitrary dimensions. Our approach provides a general framework that effectively unifies similar known techniques for constructing MDS codes. [ABSTRACT FROM AUTHOR]

This paper addresses the triangle width problem, which generalizes the classic two-machine flexible job-shop problem (FJSP) with tooling constraints. This new problem can be studied from three different angles: scheduling, matrix visualization, and vertex ordering in hypergraphs. We prove the equivalence of the different formulations of the problem and use them to establish the N P -Hardness and polynomiality of several of its subcases. This problem allows us to find more elegant (and probably shorter) proofs for several combinatorial problems in our analysis setting. Our study provides an elegant generalization of Johnson's argument for the two-machine flow shop. It also shows the relation between the question: "Is a matrix triangular?" and the "k-visit of a graph". [ABSTRACT FROM AUTHOR]

The paper concerns an analogue of the familiar Tverberg theorem, using certain staircase convex sets in place of convex hulls. For d ≥ 1 and k ≥ 2 , we obtain a number t(d, k) for which the following is true: Given a collection P of at least t(d, k) points in R d , there is a partition of P into k (nonempty, pairwise disjoint) sets S 1 , ... , S k such that the corresponding smallest boxes have a nonempty intersection. Moreover, the constructive proof offers a way to find appropriate sets S 1 , ... , S k . [ABSTRACT FROM AUTHOR]

Consider a collection of entities moving continuously with bounded speed, but otherwise unpredictably, in some low-dimensional space. Two such entities encroach upon one another at a fixed time if their separation is less than some specified threshold. Encroachment, of concern in many settings such as collision avoidance, may be unavoidable. However, the associated difficulties are compounded if there is uncertainty about the precise location of entities, giving rise to potential encroachment and, more generally, potential congestion within the full collection. We adopt a model in which entities can be queried for their current location (at some cost) and the uncertainty region associated with an entity grows in proportion to the time since that entity was last queried. The goal is to maintain low potential congestion, measured in terms of the (dynamic) intersection graph of uncertainty regions, at specified (possibly all) times, using the lowest possible query cost. Previous work in the same uncertainty model addressed the problem of minimizing the congestion potential of point entities using location queries of some bounded frequency. It was shown that it is possible to design query schemes that are O (1) -competitive, in terms of worst-case congestion potential, with other, even clairvoyant query schemes (that exploit knowledge of the trajectories of all entities), subject to the same bound on query frequency. In this paper, we initiate the treatment of a more general problem with the complementary optimization objective: minimizing the query frequency, measured as the reciprocal of the minimum time between queries (granularity), while guaranteeing a fixed bound on congestion potential of entities with positive extent at one specified target time. This complementary objective necessitates quite different schemes and analyses. Nevertheless, our results parallel those of the earlier papers, specifically tight competitive bounds on required query frequency. [ABSTRACT FROM AUTHOR]

To any simple graph G , the clique graph operator K assigns the graph K (G) , which is the intersection graph of the maximal complete subgraphs of G . The iterated clique graphs are defined by K 0 (G) = G and K n (G) = K (K n - 1 (G)) for n ≥ 1 . We associate topological concepts to graphs by means of the simplicial complex Cl (G) of complete subgraphs of G . Hence, we say that the graphs G 1 and G 2 are homotopic whenever Cl (G 1) and Cl (G 2) are. A graph G such that K n (G) ≃ G for all n ≥ 1 is called K -homotopy permanent. A graph is Helly if the collection of maximal complete subgraphs of G has the Helly property. Let G be a Helly graph. Escalante (1973) proved that K (G) is Helly, and Prisner (1992) proved that G ≃ K (G) , and so Helly graphs are K -homotopy permanent. We conjecture that if a graph G satisfies that K m (G) is Helly for some m ≥ 1 , then G is K -homotopy permanent. If a connected graph has maximum degree at most four and is different from the octahedral graph, we say that it is a low degree graph. It was recently proven that all low-degree graphs G satisfy that K 2 (G) is Helly. In this paper, we show that all low-degree graphs have the homotopy type of a wedge or circumferences, and that they are K -homotopy permanent. [ABSTRACT FROM AUTHOR]

Real networks often exhibit clustering, the tendency to form relatively small groups of nodes with high edge densities. This clustering property can cause large numbers of small and dense subgraphs to emerge in otherwise sparse networks. Subgraph counts are an important and commonly used source of information about the network structure and function. We study probability distributions of subgraph counts in a community affiliation graph. This is a random graph generated as an overlay of m partly overlapping independent Bernoulli random graphs (layers) $G_1,\dots,G_m$ with variable sizes and densities. The model is parameterised by a joint distribution of layer sizes and densities. When m grows linearly in the number of nodes n , the model generates sparse random graphs with a rich statistical structure, admitting a nonvanishing clustering coefficient and a power-law limiting degree distribution. In this paper we establish the normal and $\alpha$ -stable approximations to the numbers of small cliques, cycles, and more general 2-connected subgraphs of a community affiliation graph. [ABSTRACT FROM AUTHOR]

Understanding the intricate architecture of the brain through the lens of graph theory and advanced neuroimaging techniques has become increasingly pivotal in unraveling the complexities of neural networks. This bibliometric analysis explores the evolving landscape of brain research by focusing on the intersection of graph theoretical approaches, neuroanatomy, and diverse neuroimaging modalities. A systematic search strategy was used that resulted in the retrieval of a comprehensive dataset of articles and reviews. Using CiteSpace and VOSviewer, a detailed scientometric analysis was conducted that revealed emerging trends, key research clusters, and influential contributions within this multidisciplinary domain. Our review highlights the growing synergy between graph theory methodologies and neuroimaging modalities, reflecting the evolving paradigms shaping our understanding of brain networks. This study offers comprehensive insight into brain network research, emphasizing growth patterns, pivotal contributions, and global collaborative networks, thus serving as a valuable resource for researchers and institutions navigating this interdisciplinary landscape. [ABSTRACT FROM AUTHOR]

The leafage of a chordal graph G is the minimum integer ℓ such that G can be realized as an intersection graph of subtrees of a tree with ℓ leaves. We consider structural parameterization by the leafage of classical domination and cut problems on chordal graphs. Fomin, Golovach, and Raymond [ESA 2018, Algorithmica 2020] proved, among other things, that Dominating Set on chordal graphs admits an algorithm running in time 2 O (ℓ 2) · n O (1) . We present a conceptually much simpler algorithm that runs in time 2 O (ℓ) · n O (1) . We extend our approach to obtain similar results for Connected Dominating Set and Steiner Tree. We then consider the two classical cut problems MultiCut with Undeletable Terminals and Multiway Cut with Undeletable Terminals. We prove that the former is W[1]-hard when parameterized by the leafage and complement this result by presenting a simple n O (ℓ) -time algorithm. To our surprise, we find that Multiway Cut with Undeletable Terminals on chordal graphs can be solved, in contrast, in n O (1) -time. [ABSTRACT FROM AUTHOR]

While intersection graphs play a central role in the algorithmic analysis of hard problems on undirected graphs, the role of intersection digraphs in algorithms is much less understood. We present several contributions towards a better understanding of the algorithmic treatment of intersection digraphs. First, we introduce natural classes of intersection digraphs that generalize several classes studied in the literature. Second, we define the directed locally checkable vertex (DLCV) problems, which capture many well‐studied problems on digraphs, such as (Independent) Dominating Set, Kernel, and H $H$‐Homomorphism. Third, we give a new width measure of digraphs, bi‐mim‐width, and show that the DLCV problems are polynomial‐time solvable when we are provided a decomposition of small bi‐mim‐width. Fourth, we show that several classes of intersection digraphs have bounded bi‐mim‐width, implying that we can solve all DLCV problems on these classes in polynomial time given an intersection representation of the input digraph. We identify reflexivity as a useful condition to obtain intersection digraph classes of bounded bi‐mim‐width, and therefore to obtain positive algorithmic results. [ABSTRACT FROM AUTHOR]

Traffic state classification and relevance calculation at intersections are both difficult problems in traffic control. In this paper, we propose an intersection relevance model based on a temporal graph attention network, which can solve the above two problems at the same time. First, the intersection features and interaction time of the intersections are regarded as input quantities together with the initial labels of the traffic data. Then, they are inputted into the temporal graph attention (TGAT) model to obtain the classification accuracy of the target intersections in four states—free, stable, slow moving, and congested—and the obtained neighbouring intersection weights are used as the correlation between the intersections. Finally, it is validated by VISSIM simulation experiments. In terms of classification accuracy, the TGAT model has a higher classification accuracy than the three traditional classification models and can cope well with the uneven distribution of the number of samples. The information gain algorithm from the information entropy theory was used to derive the average delay as the most influential factor on intersection status. The correlation from the TGAT model positively correlates with traffic flow, making it interpretable. Using this correlation to control the division of subareas improves the road network's operational efficiency more than the traditional correlation model does. This demonstrates the effectiveness of the TGAT model's correlation. [ABSTRACT FROM AUTHOR]

We consider the set of graphs that can be constructed from a one-vertex graph by repeatedly adding a clique or a stable set linked to all or none of the vertices added in previous steps. This class of graphs contains various well-studied graph families such as threshold, domishold, co-domishold and complete multipartite graphs, as well as graphs with linear clique-width at most 2. We show that it can be characterized by three forbidden induced subgraphs as well as by properties involving maximal stable sets and minimal dominating sets. We also give a simple recognition algorithm and formulas for the computation of the stability and domination numbers of these graphs. [ABSTRACT FROM AUTHOR]

The goal of this paper is to show the existence (using probabilistic tools) of configurations of lines, boxes, and points with certain interesting combinatorial properties. (i) First, we construct a family of n$$ n $$ lines in ℝ3$$ {\mathbb{R}}^3 $$ whose intersection graph is triangle‐free of chromatic number Ω(n1/15)$$ \Omega \left({n}^{1/15}\right) $$. This improves the previously best known bound Ω(loglogn)$$ \Omega \left(\mathrm{loglog}n\right) $$ by Norin, and is also the first construction of a triangle‐free intersection graph of simple geometric objects with polynomial chromatic number. (ii) Second, we construct a set of n$$ n $$ points in ℝd$$ {\mathbb{R}}^d $$, whose Delaunay graph with respect to axis‐parallel boxes has independence number at most n·(logn)−(d−1)/2+o(1)$$ n\cdotp {\left(\log n\right)}^{-\left(d-1\right)/2+o(1)} $$. This extends the planar case considered by Chen, Pach, Szegedy, and Tardos. [ABSTRACT FROM AUTHOR]

Finding dense subgraphs in large (hyper)graphs is a key primitive in a variety of real-world application domains, encompassing social network analytics, event detection, biology, and finance. In most such applications, one typically aims at finding several (possibly overlapping) dense subgraphs, which might correspond to communities in social networks or interesting events. While a large amount of work is devoted to finding a single densest subgraph, perhaps surprisingly, the problem of finding several dense subgraphs in weighted hypergraphs with limited overlap has not been studied in a principled way, to the best of our knowledge. In this work, we define and study a natural generalization of the densest subgraph problem in weighted hypergraphs, where the main goal is to find at most k subgraphs with maximum total aggregate density, while satisfying an upper bound on the pairwise weighted Jaccard coefficient, i.e., the ratio of weights of intersection divided by weights of union on two nodes sets of the subgraphs. After showing that such a problem is NP-Hard, we devise an efficient algorithm that comes with provable guarantees in some cases of interest, as well as, an efficient practical heuristic. Our extensive evaluation on large real-world hypergraphs confirms the efficiency and effectiveness of our algorithms. [ABSTRACT FROM AUTHOR]

A recent trend in the context of graph theory is to bring theoretical analyses closer to empirical observations by focusing the studies on random graph models that are used to represent practical instances. There, it was observed that geometric inhomogeneous random graphs (GIRGs) yield good representations of complex real-world networks by expressing edge probabilities as a function that depends on (heterogeneous) vertex weights and distances in some underlying geometric space that the vertices are distributed in. While most of the parameters of the model are understood well, it was unclear how the dimensionality of the ground space affects the structure of the graphs. In this paper, we complement existing research into the dimension of geometric random graph models and the ongoing study of determining the dimensionality of real-world networks by studying how the structure of GIRGs changes as the number of dimensions increases. We prove that, in the limit, GIRGs approach nongeometric inhomogeneous random graphs and present insights on how quickly the decay of the geometry impacts important graph structures. In particular, we study the expected number of cliques of a given size as well as the clique number and characterize phase transitions at which their behavior changes fundamentally. Finally, our insights help in better understanding previous results about the impact of the dimensionality on geometric random graphs. [ABSTRACT FROM AUTHOR]

Predicting vehicle mobility is crucial in domains such as ride-hailing, where the balance between offer and demand is paramount. Since city road networks can be easily represented as graphs, recent works have exploited graph neural networks (GNNs) to produce more accurate predictions on real traffic data. However, a better understanding of the characteristics and limitations of this approach is needed. In this work, we compare several GNN aggregated mobility prediction schemes to a selection of other approaches in a very restricted and controlled simulation scenario. The city graph employed represents roads as directed edges and road intersections as nodes. Individual vehicle mobility is modeled as transitions between nodes in the graph. A time series of aggregated mobility is computed by counting vehicles in each node at any given time. Three main approaches are employed to construct the aggregated mobility predictors. First, the behavior of the moving individuals is assumed to follow a Markov chain (MC) model whose transition matrix is inferred via a least squares estimation procedure; the recurrent application of this MC provides the aggregated mobility prediction values. Second, a multilayer perceptron (MLP) is trained so that—given the node occupation at a given time—it can recursively provide predictions for the next values of the time series. Third, we train a GNN (according to the city graph) with the time series data via a supervised learning formulation that computes—through an embedding construction for each node in the graph—the aggregated mobility predictions. Some mobility patterns are simulated in the city to generate different time series for testing purposes. The proposed schemes are comparatively assessed compared to different baseline prediction procedures. The comparison illustrates several limitations of the GNN approaches in the selected scenario and uncovers future lines of investigation. [ABSTRACT FROM AUTHOR]

We study the following model of disease spread in a social network. At first, all individuals are either infected or healthy. Next, in discrete rounds, the disease spreads in the network from infected to healthy individuals such that a healthy individual gets infected if and only if a sufficient number of its direct neighbors are already infected. We represent the social network as a graph. Inspired by the real-world restrictions in the recent epidemic, especially by social and physical distancing requirements, we restrict ourselves to networks that can be represented as geometric intersection graphs. We show that finding a minimal vertex set of initially infected individuals to spread the disease in the whole network is computationally hard, already on unit disk graphs. Hence, to provide some algorithmic results, we focus ourselves on simpler geometric graph classes, such as interval graphs and grid graphs. [ABSTRACT FROM AUTHOR]

Given a graph G with vertex set V , a subset S of V is called a dominating set of G if every vertex is either in S or is adjacent to a vertex in S. There are a lot of variants for dominating sets, such as connected dominating sets, total dominating sets, total restricted dominating sets, secure (connected, total) dominating sets, etc. Geometric intersection graphs are graphs for which there is a bijection b between the vertices and a set P of geometric objects (for example, disks, rectangles, etc.) such that there is an edge between two vertices v and w if and only if the objects b (v) and b (w) intersect. In this paper, we offer a survey about complexity and algorithmic results on variant domination problems in geometric intersection graphs. [ABSTRACT FROM AUTHOR]

Chordal graphs are characterized as the intersection graphs of subtrees in a tree and such a representation is known as the tree model. Restricting the characterization results in well-known subclasses of chordal graphs such as interval graphs or split graphs. A typical example of a problem that does not behave computationally the same in all subclasses of chordal graphs is the Subset Feedback Vertex Set (SFVS) problem: given a vertex-weighted graph G = (V , E) and a set S ⊆ V , we seek for a vertex set of minimum weight that intersects all cycles containing a vertex of S. SFVS is known to be polynomial-time solvable on interval graphs, whereas SFVS remains np-complete on split graphs and, consequently, on chordal graphs. Towards a better understanding of the complexity of SFVS on subclasses of chordal graphs, we exploit structural properties of a tree model in order to cope with the hardness of SFVS. Here we consider the leafage, which measures the minimum number of leaves in a tree model. We show that SFVS can be solved in polynomial time for every chordal graph with bounded leafage. In particular, given a chordal graph on n vertices with leafage ℓ , we provide an algorithm for solving SFVS with running time n O (ℓ) , thus improving upon n O (ℓ 2) , which is the running time of an approach that utilizes the previously known algorithm for graphs with bounded mim-width. We complement our result by showing that SFVS is w[1]-hard parameterized by ℓ . Pushing further our positive result, it is natural to also consider the vertex leafage, which measures the minimum upper bound on the number of leaves of every subtree in a tree model. However, we show that it is unlikely to obtain a similar result, as we prove that SFVS remains np-complete on undirected path graphs, i.e., chordal graphs having vertex leafage at most two. Lastly, we provide a polynomial-time algorithm for solving SFVS on rooted path graphs, a proper subclass of undirected path graphs and graphs with mim-width one, which is faster than the approach of constructing a graph decomposition of mim-width one and applying the previously known algorithm for graphs with bounded mim-width. [ABSTRACT FROM AUTHOR]

Recent advances in mobile mapping systems have facilitated the collection of high-precision trajectory data in centimeter positioning accuracy. It provides the potential to infer lane-level road networks, which are essential for autonomous driving navigation. This task is challenging due to the complicated lane merging and diverging structures as well as the lane-changing patterns in trajectory data. This paper presents a lane-level road network generation method from high-precision trajectory data with lane-changing behavior analysis. Trajectories are firstly partitioned by detecting road intersections and changes in lane structure. Subsequently, in regions with consistent lane structure, a principal curve fitting algorithm is developed to extract lane centerlines. Erroneous lanes generated by lane-changing behavior are pruned based on a constructed lane intersection graph. In regions with merging and diverging lanes, a lane-group fitting algorithm is designed. This algorithm estimates lane locations by incorporating a Gaussian mixture model with lane width prior knowledge and then infers lane-level topological structures using trajectory flow information. The proposed method is evaluated on a real-world high-precision trajectory dataset. Comprehensive experiments demonstrate that it outperforms state-of-the-art methods in four metrics. Under complex scenarios, the method is capable of generating lane-level road networks with higher completeness and fewer fragments. [ABSTRACT FROM AUTHOR]

We prove that, for every graph F with at least one edge, there is a constant c F such that there are graphs of arbitrarily large chromatic number and the same clique number as F in which every F-free induced subgraph has chromatic number at most c F . This generalises recent theorems of Briański, Davies and Walczak, and Carbonero, Hompe, Moore and Spirkl. Our results imply that for every r ⩾ 3 the class of K r -free graphs has a very strong vertex Ramsey-type property, giving a vast generalisation of a result of Folkman from 1970. We also prove related results for tournaments, hypergraphs and infinite families of graphs, and show an analogous statement for graphs where clique number is replaced by odd girth. [ABSTRACT FROM AUTHOR]

The essential annihilating-ideal graph E G (R) of a commutative unital ring R is a simple graph, whose vertices are non-zero ideals of R with non-zero annihilator and there exists an edge between two distinct vertices I, J if and only if Ann(IJ) has a non-zero intersection with any non-zero ideal of R. In this paper, we show that E G (R) is weakly perfect, if R is Noetherian and an explicit formula for the clique number of E G (R) is given. Moreover, the structures of all rings whose essential annihilating-ideal graphs have chromatic number 2 are fully determined. Among other results, twin-free clique number and edge chromatic number of E G (R) are examined. [ABSTRACT FROM AUTHOR]

Let S ⊆ R 2 be a set of nsites in the plane, so that every site s ∈ S has an associated radius r s > 0 . Let D (S) be the disk intersection graph defined by S, i.e., the graph with vertex set S and an edge between two distinct sites s , t ∈ S if and only if the disks with centers s, t and radii r s , r t intersect. Our goal is to design data structures that maintain the connectivity structure of D (S) as sites are inserted and/or deleted in S. First, we consider unit disk graphs, i.e., we fix r s = 1 , for all sites s ∈ S . For this case, we describe a data structure that has O (log 2 n) amortized update time and O (log n / log log n) query time. Second, we look at disk graphs with bounded radius ratio Ψ , i.e., for all s ∈ S , we have 1 ≤ r s ≤ Ψ , for a parameter Ψ that is known in advance. Here, we not only investigate the fully dynamic case, but also the incremental and the decremental scenario, where only insertions or only deletions of sites are allowed. In the fully dynamic case, we achieve amortized expected update time O (Ψ log 4 n) and query time O (log n / log log n) . This improves the currently best update time by a factor of Ψ . In the incremental case, we achieve logarithmic dependency on Ψ , with a data structure that has O (α (n)) amortized query time and O (log Ψ log 4 n) amortized expected update time, where α (n) denotes the inverse Ackermann function. For the decremental setting, we first develop an efficient decremental disk revealing data structure: given two sets R and B of disks in the plane, we can delete disks from B, and upon each deletion, we receive a list of all disks in R that no longer intersect the union of B. Using this data structure, we get decremental data structures with a query time of O (log n / log log n) that supports deletions in O (n log Ψ log 4 n) overall expected time for disk graphs with bounded radius ratio Ψ and O (n log 5 n) overall expected time for disk graphs with arbitrary radii, assuming that the deletion sequence is oblivious of the internal random choices of the data structures. [ABSTRACT FROM AUTHOR]

A circle graph is an intersection graph of a set of chords of a circle. We describe the unavoidable induced subgraphs of circle graphs with large treewidth. This includes examples that are far from the "usual suspects." Our results imply that treewidth and Hadwiger number are linearly tied on the class of circle graphs and that the unavoidable induced subgraphs of a vertex-minor-closed class with large treewidth are the usual suspects if and only if the class has bounded rank-width. Using the same tools, we also study the treewidth of graphs G that have a circular drawing whose crossing graph is well-behaved in some way. In this setting, we show that if the crossing graph is Kt-minor-free, then G has treewidth at most 12t 23 and has no K2,4t-topological minor. On the other hand, we show that there are graphs with arbitrarily large Hadwiger number that have circular drawings whose crossing graphs are 2-degenerate. [ABSTRACT FROM AUTHOR]

If H = (V, ε) is a hypergraph, its edge intersection hypergraph EI(H) = (V, εEI) has the edge set εEI = {e1 ∩ e2 | e1, e2 ∈ ε ∧ e1 ≠ e2 ∧ |e1 ∩ e2| ≥ 2}. Besides investigating several structural properties of edge intersection hypergraphs, we prove that all trees but seven exceptional ones are edge intersection hypergraphs of 3-uniform hypergraphs. Using the so-called clique-fusion, as a conclusion we obtain that nearly all cacti are edge intersection hypergraphs of 3-uniform hypergraphs, too. [ABSTRACT FROM AUTHOR]

A subvariety of a quasi-projective complex variety X is called "universally irreducible" if its preimage inside the universal cover of X is irreducible. In this paper we investigate sufficient conditions for universal irreducibility. We consider in detail complete intersection subvarieties of small codimension inside Siegel moduli spaces of any finite level. Moreover, we show that, for g ≥ 3 , every Siegel modular form is the product of finitely many irreducible analytic functions on the Siegel upper half-space ℍ g . We also discuss the special case of singular theta series of weight 1 2 and of Schottky forms. [ABSTRACT FROM AUTHOR]

In 2020, we initiated a systematic study of graph classes in which the treewidth can only be large due to the presence of a large clique, which we call (tw , ω) -bounded. The family of (tw , ω) -bounded graph classes provides a unifying framework for a variety of very different families of graph classes, including graph classes of bounded treewidth, graph classes of bounded independence number, intersection graphs of connected subgraphs of graphs with bounded treewidth, and graphs in which all minimal separators are of bounded size. While Chaplick and Zeman showed in 2017 that (tw , ω) -bounded graph classes enjoy some good algorithmic properties related to clique and coloring problems, it is an interesting open problem to which extent (tw , ω) -boundedness has useful algorithmic implications for problems related to independent sets. We provide a partial answer to this question by identifying a sufficient condition for (tw , ω) -bounded graph classes to admit a polynomial-time algorithm for the Maximum Weight Independent Packing problem and, as a consequence, for the weighted variants of the Independent Set and Induced Matching problems. Our approach is based on a new min-max graph parameter related to tree decompositions. We define the independence number of a tree decomposition T of a graph as the maximum independence number over all subgraphs of G induced by some bag of T. The tree-independence number of a graph G is then defined as the minimum independence number over all tree decompositions of G. Boundedness of the tree-independence number is a refinement of (tw , ω) -boundedness that is still general enough to hold for all the aforementioned families of graph classes. Generalizing a result on chordal graphs due to Cameron and Hell from 2006, we show that if a graph is given together with a tree decomposition with bounded independence number, then the Maximum Weight Independent Packing problem can be solved in polynomial time. Applications of our general algorithmic result to specific graph classes are given in the third paper of the series [Dallard, Milanič, and Štorgel, Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure]. [ABSTRACT FROM AUTHOR]

The disjointness graph of a set system is a graph whose vertices are the sets, two being connected by an edge if and only if they are disjoint. It is known that the disjointness graph G of any system of segments in the plane is χ-bounded , that is, its chromatic number χ (G) is upper bounded by a function of its clique number ω (G). Here we show that this statement does not remain true for systems of polygonal chains of length 2. We also construct systems of polygonal chains of length 3 such that their disjointness graphs have arbitrarily large girth and chromatic number. In the opposite direction, we show that the class of disjointness graphs of (possibly self-intersecting) 2 -way infinite polygonal chains of length 3 is χ -bounded: for every such graph G , we have χ (G) ≤ (ω (G)) 3 + ω (G). [ABSTRACT FROM AUTHOR]

Interval graphs are the intersection graphs of intervals on the real line. Unit interval graphs are interval graphs representable by intervals of unit length. Rautenbach and Szwarcfiter showed that the class of intersection graphs of the open and closed real intervals of unit length is a strict superclass of the class of unit interval graphs. They also characterized this class of graphs. An interval bigraph is a bipartite graph where to each vertex we can assign an interval so that vertices in the opposite partite sets are adjacent if and only if their intervals intersect. Analogously we show that the class of finite intersection bigraphs of open and closed intervals of unit length is a strict superclass of the class of unit interval bigraphs. We also characterize this class of bigraphs in terms of forbidden induced subgraphs and a suitable extension of proper interval bigraphs. [ABSTRACT FROM AUTHOR]

We investigate the enumeration problems for the class of distance-hereditary graphs and related graph classes. We first give an enumeration algorithm for the class of distance-hereditary graphs using the recent framework for enumerating every non-isomorphic element in a graph class. In the algorithm, we use the vertex-incremental characterization of distance-hereditary graphs, which consists of three generation rules for adding one vertex to a distance-hereditary graph. Reducing the three generation rules, we can obtain vertex-incremental characterization of cographs and (6,2)-chordal bipartite graphs. These enumeration algorithms are slower than previously known theoretical enumeration algorithms, however, ours are easy to implement. In fact, we implemented our algorithm and obtained catalogs of these graph classes of up to 15 vertices. The class of Ptolemaic graphs is an intersection of the class of chordal graphs and the class of distance-hereditary graphs. We modify the enumeration algorithm for distance-hereditary graphs and obtain an enumeration algorithm for Ptolemaic graphs. The running time of the enumeration of Ptolemaic graphs is much improved from the previously known one, and we also enumerated the graphs up to 15 vertices. We also enumerate the class of 3-leaf power graphs by modifying the algorithm for Ptolemaic graphs. As far as the authors know, some of these graph classes had been counted, however, they had never been enumerated. [ABSTRACT FROM AUTHOR]