Fan-Planar Graphs: Combinatorial Properties and Complexity Results

Binucci, Carla and Di Giacomo, Emilio and Didimo, Walter and Montecchiani, Fabrizio and Patrignani, Maurizio and Tollis, Ioannis G. (2014) Fan-Planar Graphs: Combinatorial Properties and Complexity Results. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014 , pp. 186-197(Official URL:

Full text not available from this repository.


In a fan-planar drawing 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 5n − 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 drawings and study the relationship between fan-planarity and k-planarity. Also, we prove that testing fan-planarity in the variable embedding setting is NP-complete.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-662-45803-7_16
Classifications: G Algorithms and Complexity > G.420 Crossings
P Styles > P.480 Layered
P Styles > P.540 Planar
P Styles > P.999 Others
Z Theory > Z.750 Topology
Z Theory > Z.999 Others

Actions (login required)

View Item View Item