Name
Abstract | ||
|---|---|---|
In a \emph{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 \geq 20$. We extend their result, both from 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. Furthermore, we prove that deciding whether a graph admits a fan-planar drawing in the variable embedding setting is NP-complete. |
Year | Venue | Field |
|---|---|---|
2014 | CoRR | Discrete mathematics,Graph,Combinatorics,Planarity testing,Embedding,Force-directed graph drawing,Mathematics |
DocType | Volume | Citations |
Journal | abs/1406.5299 | 2 |
PageRank | References | Authors |
0.35 | 13 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Carla Binucci | 1 | 103 | 16.18 |
| Emilio Di Giacomo | 2 | 449 | 43.85 |
| Walter Didimo | 3 | 943 | 76.56 |
| Fabrizio Montecchiani | 4 | 261 | 37.42 |
| Maurizio Patrignani | 5 | 675 | 61.47 |
| Ioannis G. Tollis | 6 | 1240 | 162.75 |