Home Issues About JGAA Instructions for Authors
 
 
Special issue on Selected papers from the Twenty-nineth International Symposium on Graph Drawing and Network Visualization, GD 2021
DOI: 10.7155/jgaa.00618
Simplifying Non-Simple Fan-Planar Drawings
Vol. 27, no. 2, pp. 147-172, 2023. Regular paper.
Abstract 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.
 This work is licensed under the terms of the CC-BY license.
Submitted: December 2021.
Reviewed: April 2022.
Revised: May 2022.
Accepted: October 2022.
Final: February 2023.
Published: February 2023.
Communicated by Ignaz Rutter and Helene Purchase
article (PDF)
BibTeX