DROPS

Document

Poster Abstract

DOI: 10.4230/LIPIcs.GD.2024.54

Approximating the Crossing Number of Dense Graphs (Poster Abstract)

Authors: Oriol Solé Pi

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract

We present a deterministic n^(2+o(1))-time algorithm that approximates the crossing number of any graph G of order n up to an additive error of o(n⁴), as well as a randomized polynomial-time algorithm that constructs a drawing of G with cr(G)+o(n⁴) crossings. These results imply a (1+o(1))-approximation algorithm for the crossing number of dense graphs. Our work builds on the machinery used by Fox, Pach and Súk [Fox et al., 2016], who obtained similar results for the rectilinear crossing number.

Cite as

Oriol Solé Pi. Approximating the Crossing Number of Dense Graphs (Poster Abstract). In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 54:1-54:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{solepi:LIPIcs.GD.2024.54,
  author =	{Sol\'{e} Pi, Oriol},
  title =	{{Approximating the Crossing Number of Dense Graphs}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{54:1--54:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.54},
  URN =		{urn:nbn:de:0030-drops-213387},
  doi =		{10.4230/LIPIcs.GD.2024.54},
  annote =	{Keywords: Crossing numbers, Approximation algorithms, Geometric graph theory}
}

Search Results

Documents authored by Solé Pi, Oriol

Approximating the Crossing Number of Dense Graphs (Poster Abstract)

Abstract

Cite as

Thanks for your feedback!

Could not send message