New Bounds on the Maximum Number of Edges in k-Quasi-Planar Graphs
Graph Chatbot
Chat with Graph Search
Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.
DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.
Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small ...
We approach the graph generation problem from a spectral perspective by first generating the dominant parts of the graph Laplacian spectrum and then building a graph matching these eigenvalues and eigenvectors. Spectral conditioning allows for direct model ...
Can one reduce the size of a graph without significantly altering its basic properties? The graph reduction problem is hereby approached from the perspective of restricted spectral approximation, a modification of the spectral similarity measure used for g ...
An abstract topological graph (briefly an AT-graph) is a pair A = (G, X) where G = (V, E) is a graph and X. E2 is a set of pairs of its edges. The AT-graph A is simply realizable if G can be drawn in the plane so that each pair of edges from X crosses exac ...
Graph neural networks take node features and graph structure as input to build representations for nodes and graphs. While there are a lot of focus on GNN models, understanding the impact of node features and graph structure to GNN performance has received ...
We consider the problem of inferring a matching hidden in a weighted random k-hypergraph. We assume that the hyperedges' weights are random and distributed according to two different densities conditioning on the fact that they belong to the hidden matchin ...
We considerm-colorings of the edges of a complete graph, where each color class is defined semi-algebraically with bounded complexity. The casem= 2 was first studied by Alon et al., who applied this framework to obtain surprisingly strong Ramsey-type resul ...
Given two graphs H and F, the maximum possible number of copies of H in an F-free graph on n vertices is denoted by ex(n, H, F). We investigate the function ex(n, H, kF), where kF denotes k vertex disjoint copies of a fixed graph F. Our results include cas ...
In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...
