On the Density of Non-simple 3-Planar Graphs

A k-planar graph is a graph that can be drawn in the plane such that every edge is crossed at most k times. For \(k \le 4\) , Pach and Tóth [20 ] proved a bound of \((k+3)(n-2)\) on the total number of edges of a k-planar graph, which is tight for \(k=1,2

  • PDF / 427,864 Bytes
  • 13 Pages / 439.37 x 666.142 pts Page_size
  • 113 Downloads / 163 Views

DOWNLOAD

REPORT


2

Institut f¨ ur Informatik, Universit¨ at T¨ ubingen, Tubingen, Germany {bekos,mk}@informatik.uni-tuebingen.de School of Applied Mathematics and Physical Sciences, NTUA, Athens, Greece [email protected]

Abstract. A k-planar graph is a graph that can be drawn in the plane such that every edge is crossed at most k times. For k ≤ 4, Pach and T´ oth [20] proved a bound of (k + 3)(n − 2) on the total number of edges of a k-planar graph, which is tight for k = 1, 2. For k = 3, the bound of n − 11 in [19] and has been shown to be 6n − 12 has been improved to 11 2 optimal up to an additive constant for simple graphs. In this paper, we n−11 edges also holds for non-simple 3-planar prove that the bound of 11 2 graphs that admit drawings in which non-homotopic parallel edges and self-loops are allowed. Based on this result, a characterization of optimal 3-planar graphs (that is, 3-planar graphs with n vertices and exactly 11 n − 11 edges) might be possible, as to the best of our knowledge the 2 densest known simple 3-planar is not known to be optimal.

1

Introduction

Planar graphs play an important role in graph drawing and visualization, as the avoidance of crossings and occlusions is central objective in almost all applications [10,18]. The theory of planar graphs [15] could be very nicely applied and used for developing great layout algorithms [13,22,23] based on the planarity concepts. Unfortunately, real-world graphs are usually not planar despite of their sparsity. With this background, an initiative has formed in recent years to develop a suitable theory for nearly planar graphs, that is, graphs with various restrictions on their crossings, such as limitations on the number of crossings per edge (e.g., k-planar graphs [21]), avoidance of local crossing configurations (e.g., quasi planar graphs [2], fan-crossing free graphs [9], fan-planar graphs [17]) or restrictions on the crossing angles (e.g., RAC graphs [11], LAC graphs [12]). For precise definitions, we refer to the literature mentioned above. The most prominent is clearly the concept of k-planar graphs, namely graphs that allow drawings in the plane such that each edge is crossed at most k times by other edges. The simplest case k = 1, i.e., 1-planar graphs [21], has been subject of intensive research in the past and it is quite well understood, see e.g. [4,6–8,14,20]. For k ≥ 2, the picture is much less clear. Only few papers on special cases appeared, see e.g., [3,16]. This work has been supported by DFG grant Ka812/17-1. c Springer International Publishing AG 2016  Y. Hu and M. N¨ ollenburg (Eds.): GD 2016, LNCS 9801, pp. 344–356, 2016. DOI: 10.1007/978-3-319-50106-2 27

On the Density of Non-simple 3-Planar Graphs

345

Pach and T´ oth’s paper [20] stands out and contributed a lot to the understanding of nearly planar graphs. The paper considers the number of edges in simple k-planar graphs for general k. Note the well-known bound of 3n − 6 edges for planar graphs deducible from Euler’s formula. For small k = 1, 2, 3 and 4, bounds of 4n − 8, 5n − 10,