NDLI: The Number of Edges in $k$-Quasi-planar Graphs

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Pach, János Fox, Jacob Suk, Andrew
Copyright Year	2013
Abstract	A graph drawn in the plane is called $k$-quasi-planar if it does not contain $k$ pairwise crossing edges. It has been conjectured for a long time that for every fixed $k$, the maximum number of edges of a $k$-quasi-planar graph with $n$ vertices is $O(n)$. The best known upper bound is $n(\log n)^{O(\log k)}$. In the present paper, we improve this bound to $(n\log n )2^{\alpha(n)^{c_k}}$ in the special case where the graph is drawn in such a way that every pair of edges meet at most once. Here $\alpha(n)$ denotes the (extremely slowly growing) inverse of the Ackermann function. We also make further progress on the conjecture for $k$-quasi-planar graphs in which every edge is drawn as an $x$-monotone curve. Extending some ideas of Valtr, we prove that the maximum number of edges of such graphs is at most $2^{ck^6}n\log n$.
Starting Page	550
Ending Page	561
Page Count	12
File Format	PDF
ISSN	08954801
DOI	10.1137/110858586
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	1
Volume Number	27
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2013-03-19
Access Restriction	Subscribed
Subject Keyword	Planar graphs; geometric and topological aspects of graph theory Turan-type problems Erdős problems and related topics of discrete geometry topological graphs Graph theory Extremal problems quasi-planar graphs
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Density Theorems for Intersection Graphs of $t$-Monotone Curves

Crossing Stars in Topological Graphs

On the Number of Edges in Geometric Graphs Without Empty Triangles

The Bar Visibility Number of a Graph

On the Pagenumber of k-Trees

New bounds on the maximum number of edges in $k$-quasi-planar graphs

Bounding the number of edges of matchstick graphs

Bounds on the Maximum Multiplicity of Some Common Geometric Graphs

A Tight Lower Bound on the Size of Planar Permutation Networks

The Number of Edges in $k$-Quasi-planar Graphs

Similar Documents

Density Theorems for Intersection Graphs of $t$-Monotone Curves

Crossing Stars in Topological Graphs

On the Number of Edges in Geometric Graphs Without Empty Triangles

The Bar Visibility Number of a Graph

On the Pagenumber of k-Trees

New bounds on the maximum number of edges in $k$-quasi-planar graphs

Bounding the number of edges of matchstick graphs

Bounds on the Maximum Multiplicity of Some Common Geometric Graphs

A Tight Lower Bound on the Size of Planar Permutation Networks

The Number of Edges in $k$-Quasi-planar Graphs