文章基本信息

标题：On Optimal 2- and 3-Planar Graphs
本地全文：下载
作者：Michael A. Bekos ; Michael Kaufmann ; Chrysanthi N. Raftopoulou 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：77
页码：16:1-16:16
DOI：10.4230/LIPIcs.SoCG.2017.16
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：topological graphs; optimal k-planar graphs; characterization