Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
437722 | Theoretical Computer Science | 2015 | 11 Pages |
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 [35], who proved that every n -vertex fan-planar drawing has at most 5n−105n−10 edges, and that this bound is tight for n≥20n≥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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Carla Binucci, Emilio Di Giacomo, Walter Didimo, Fabrizio Montecchiani, Maurizio Patrignani, Antonios Symvonis, Ioannis G. Tollis,