Geodesic
Simplifying Non-Simple Fan-Planar Drawings
Journal of Graph Algorithms and Applications, Special issue on Selected papers from the Twenty-nineth International Symposium on Graph Drawing and Network Visualization, GD 2021 , Tome 27 (2023) no. 2, pp. 147-172.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

A drawing of a graph is fan-planar if the edges intersecting a common edge $a$ share a vertex $A$ on the same side of $a$. More precisely, orienting $a$ arbitrarily and the other edges towards $A$ results in a consistent orientation of the crossings. So far, fan-planar drawings have only been considered in the context of simple drawings, where any two edges share at most one point, including endpoints. We show that every non-simple fan-planar drawing can be redrawn as a simple fan-planar drawing of the same graph while not introducing additional crossings. The proof is constructive and corresponds to a quadratic time algorithm. Combined with previous results on fan-planar drawings, this yields that $n$-vertex graphs having such a drawing can have at most $6.5n-20$ edges and that the recognition of such graphs is NP-hard. We thereby answer an open problem posed by Kaufmann and Ueckerdt in 2014.
DOI : 10.7155/jgaa.00618
Keywords: Fan-planar graphs, Simple topological graphs, Beyond-planar graphs, Graph drawing 
@article{JGAA_2023_27_2_a5,
     author = {Boris Klemz and Kristin Knorr and Meghana Reddy and Felix Schr\"oder},
     title = {Simplifying {Non-Simple} {Fan-Planar} {Drawings}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {147--172},
     publisher = {mathdoc},
     volume = {27},
     number = {2},
     year = {2023},
     doi = {10.7155/jgaa.00618},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00618/}
}
TY  - JOUR
AU  - Boris Klemz
AU  - Kristin Knorr
AU  - Meghana Reddy
AU  - Felix Schröder
TI  - Simplifying Non-Simple Fan-Planar Drawings
JO  - Journal of Graph Algorithms and Applications
PY  - 2023
SP  - 147
EP  - 172
VL  - 27
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00618/
DO  - 10.7155/jgaa.00618
LA  - en
ID  - JGAA_2023_27_2_a5
ER  - 
%0 Journal Article
%A Boris Klemz
%A Kristin Knorr
%A Meghana Reddy
%A Felix Schröder
%T Simplifying Non-Simple Fan-Planar Drawings
%J Journal of Graph Algorithms and Applications
%D 2023
%P 147-172
%V 27
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00618/
%R 10.7155/jgaa.00618
%G en
%F JGAA_2023_27_2_a5
Boris Klemz; Kristin Knorr; Meghana Reddy; Felix Schröder. Simplifying Non-Simple Fan-Planar Drawings. Journal of Graph Algorithms and Applications, 
							Special issue on Selected papers from the Twenty-nineth International Symposium on Graph Drawing and Network Visualization, GD 2021
					, Tome 27 (2023) no. 2, pp. 147-172. doi : 10.7155/jgaa.00618. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00618/

Cité par Sources :