Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
New Bounds on the Maximum Number of Edges in k-Quasi-Planar Graphs
verfasst von : Andrew Suk, Bartosz Walczak
Erschienen in: Graph Drawing
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
(log
k
)
edges. We improve this upper bound to
$2^{\alpha(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^{\alpha(n)^c}n\log n$
obtained by Fox, Pach, and Suk.