Fan-Planar Graphs: Combinatorial Properties and Complexity Results - Graph Drawing - page 185

Fan-Planar Graphs: Combinatorial Properties
and Complexity Results

Carla Binucci 1 , Emilio Di Giacomo 1 , Walter Didimo 1 , Fabrizio Montecchiani 1 ,
Maurizio Patrignani 2 , and Ioannis G. Tollis 3

1 Universit`adegli Studi di Perugia, Italy
{ carla.binucci,emilio.digiacomo,
walter.didimo,fabrizio.montecchiani } @unipg.it
2 Universit`aRomaTre,Italy
[e-mail]

3

Univ. of Crete and Institute of Computer Science-FORTH, Greece
[e-mail]

Abstract. In a fan-planardrawing of a graph an edge can cross only edges with
a common end-vertex. Fan-planar drawings have been recently introduced by
Kaufmann and Ueckerdt, who proved that every n -vertex fan-planar drawing has
at most 5 n − 10 edges, and that this bound is tight for n ≥ 20. We extend their
result from both the combinatorial and the algorithmic point of view. We prove
tight bounds on the density of constrained versions of fan-planar drawingsand
study the relationship between fan-planarity and k -planarity. Also, we prove that
testing fan-planarity in the variable embedding setting is NP-complete.

1 Introduction

There is a growing interest in the study of non-planar drawingsofgraphs with forbidden
crossing configurations. The idea is to relax the planarity constraint by allowing edge
crossings that do not affect too much the drawing readability. Among the most popular
types of non-planar drawingsstudied so far we recall: k -planardrawings ,wherean
edge can have at most k crossings (see, e.g., [5,8,9,10,16,18,22,26,27,29,30,32]);
k -quasi-planardrawings , which do not contain k mutually crossing edges (see,
e.g., [1,3,4,15,24,33]); RAC drawings ,whereedges can cross only at right angles (see,
e.g., [19] and [20] for a survey); ACE ʱ drawings [2] and ACL ʱ drawings [6,14,21],
which are generalizations of RAC drawings;namely,inanACE ʱ drawing edges can
cross only at an angle that is exactly ʱ ( ʱ (0 ,ˀ/ 2]); in an ACL ʱ drawing edges can

cross only at angles that are atleast ʱ (see also [20]); fan-crossing free drawings ,where
there cannot be an edge that crosses two other edges with a common end-vertex [11].
Given a desired type T of non-planar drawing with forbidden crossing configu-
rations, a classical combinatorial problem is to establish bounds on the maximum

∈

Research supported in part by the MIUR project AMANDA “Algorithmics for MAssive and
Networked DAta”, prot. 2012C4E3KT 001. This work started at the Bertinoro Workshop on
Graph Drawing 2014. We thank Michael Kaufmann and Torsten Ueckerdt for suggesting the
study of fan-planar graphs during the workshop. We also thank all the participants of the
workshop for the usefuldiscussions on this topic.