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: http://dx.doi.org/10.1007/978-3-662-45803-7_16).

Full text not available from this repository.

Abstract

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
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 22 May 2015 09:02
Last Modified: 22 May 2015 13:17
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1432

Actions (login required)

View Item View Item