License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.28
URN: urn:nbn:de:0030-drops-99763
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9976/
Go to the corresponding LIPIcs Volume Portal

Angelini, Patrizio ; Bekos, Michael A. ; Kaufmann, Michael ; Pfister, Maximilian ; Ueckerdt, Torsten

Beyond-Planarity: Turán-Type Results for Non-Planar Bipartite Graphs

pdf-format:
LIPIcs-ISAAC-2018-28.pdf (0.7 MB)

Abstract

Beyond-planarity focuses on the study of geometric and topological graphs that are in some sense nearly planar. Here, planarity is relaxed by allowing edge crossings, but only with respect to some local forbidden crossing configurations. Early research dates back to the 1960s (e.g., Avital and Hanani 1966) for extremal problems on geometric graphs, but is also related to graph drawing problems where visual clutter due to edge crossings should be minimized (e.g., Huang et al. 2018).
Most of the literature focuses on Turán-type problems, which ask for the maximum number of edges a beyond-planar graph can have. Here, we study this problem for bipartite topological graphs, considering several types of beyond-planar graphs, i.e. 1-planar, 2-planar, fan-planar, and RAC graphs. We prove bounds on the number of edges that are tight up to additive constants; some of them are surprising and not along the lines of the known results for non-bipartite graphs. Our findings lead to an improvement of the leading constant of the well-known Crossing Lemma for bipartite graphs, as well as to a number of interesting questions on topological graphs.

BibTeX - Entry

@InProceedings{angelini_et_al:LIPIcs:2018:9976,
  author =	{Patrizio Angelini and Michael A. Bekos and Michael Kaufmann and Maximilian Pfister and Torsten Ueckerdt},
  title =	{{Beyond-Planarity: Tur{\'a}n-Type Results for Non-Planar Bipartite Graphs}},
  booktitle =	{29th International Symposium on Algorithms and Computation  (ISAAC 2018)},
  pages =	{28:1--28:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9976},
  URN =		{urn:nbn:de:0030-drops-99763},
  doi =		{10.4230/LIPIcs.ISAAC.2018.28},
  annote =	{Keywords: Bipartite topological graphs, beyond planarity, density, Crossing Lemma}
}

Keywords: Bipartite topological graphs, beyond planarity, density, Crossing Lemma
Collection: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 06.12.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI