Publication

New Bounds on the Maximum Number of Edges in k-Quasi-Planar Graphs

2013
Conference Papers

Abstract

A topological graph is k-quasi-planar if it does not contain k pairwise crossing edges. An old conjecture states that for every fixed k, the maximum number of edges in a k-quasi-planar graph on n vertices is O(n). Fox and Pach showed that every k-quasi-planar graph with n vertices and no pair of edges intersecting in more than O(1) points has at most n(log n)O(logk) edges. We improve this upper bound to 2α(n)c n log n, where α(n) denotes the inverse Ackermann function, and c depends only on k. We also show that every k-quasi-planar graph with n vertices and every two edges have at most one point in common has at most O(n log n) edges. This improves the previously known upper bound of 2α(n)c n log n obtained by Fox, Pach, and Suk. © 2013 Springer International Publishing Switzerland.

Official source

https://infoscience.epfl.ch/entities/publication/0321ba40-b0a2-4a86-843f-c7296d65a8e1

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

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.

2013
Conference Papers

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/0321ba40-b0a2-4a86-843f-c7296d65a8e1

About this result

Related concepts (31)

Graph minor

In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges, vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if its minors include neither the complete graph K5 nor the complete bipartite graph K3,3. The Robertson–Seymour theorem implies that an analogous forbidden minor characterization exists for every property of graphs that is preserved by deletions and edge contractions.

Chordal graph

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree.

Bipartite graph

In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets and , that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles. The two sets and may be thought of as a coloring of the graph with two colors: if one colors all nodes in blue, and all nodes in red, each edge has endpoints of differing colors, as is required in the graph coloring problem.

Related publications (8)

New Bounds on the Maximum Number of Edges in k-Quasi-Planar Graphs

Chat with Graph Search

Tight bounds for intersection‐reverse sequences, edge‐ordered graphs, and applications

Scalable Parallel and Distributed Simulation of an Epidemic on a Graph

Scaling a Reliable Distributed System