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.SoCG.2017.16
URN: urn:nbn:de:0030-drops-72307
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7230/
Go to the corresponding LIPIcs Volume Portal

Bekos, Michael A. ; Kaufmann, Michael ; Raftopoulou, Chrysanthi N.

On Optimal 2- and 3-Planar Graphs

pdf-format:
LIPIcs-SoCG-2017-16.pdf (1 MB)

Abstract

A graph is k-planar if it can be drawn in the plane such that no edge is crossed more than k times. While for k=1, optimal 1-planar graphs, i.e., those with n vertices and exactly 4n-8 edges, have been completely characterized, this has not been the case for k > 1. For k=2,3 and 4, upper bounds on the edge density have been developed for the case of simple graphs by Pach and Tóth, Pach et al. and Ackerman, which have been used to improve the well-known "Crossing Lemma". Recently, we proved that these bounds also apply to non-simple 2- and 3-planar graphs without homotopic parallel edges and self-loops.

In this paper, we completely characterize optimal 2- and 3-planar graphs, i.e., those that achieve the aforementioned upper bounds. We prove that they have a remarkably simple regular structure, although they might be non-simple. The new characterization allows us to develop notable insights concerning new inclusion relationships with other graph classes.

BibTeX - Entry

@InProceedings{bekos_et_al:LIPIcs:2017:7230,
  author =	{Michael A. Bekos and Michael Kaufmann and Chrysanthi N. Raftopoulou},
  title =	{{On Optimal 2- and 3-Planar Graphs}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{16:1--16:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Boris Aronov and Matthew J. Katz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7230},
  URN =		{urn:nbn:de:0030-drops-72307},
  doi =		{10.4230/LIPIcs.SoCG.2017.16},
  annote =	{Keywords: topological graphs, optimal k-planar graphs, characterization}
}

Keywords: topological graphs, optimal k-planar graphs, characterization
Collection: 33rd International Symposium on Computational Geometry (SoCG 2017)
Issue Date: 2017
Date of publication: 20.06.2017

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