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 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 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.
Binucci, C., Di Giacomo, E., Didimo, W., Montecchiani, F., Patrignani, M., Symvonis, A., et al. (2015). Fan-planarity: Properties and complexity. THEORETICAL COMPUTER SCIENCE, 589, 76-86 [10.1016/j.tcs.2015.04.020].
Fan-planarity: Properties and complexity
PATRIGNANI, Maurizio;
2015-01-01
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 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 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.| File | Dimensione | Formato | |
|---|---|---|---|
|
Fan-planarity - Properties and complexity (TCS 2015 submitted).pdf
accesso aperto
Descrizione: Preprint submitted to editor
Tipologia:
Documento in Pre-print
Licenza:
DRM non definito
Dimensione
496.17 kB
Formato
Adobe PDF
|
496.17 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
