Journal of Graph Algorithms and Applications
|Home||Issues||Aims and Scope||Instructions for Authors|
This paper has been accepted to be published in the JGAA Special Issue on Graph Drawing Beyond Planarity. The paper will receive a volume, an issue number, and page numbers when the whole special issue will be published.
On the size of planarly connected crossing graphs
Eyal Ackerman, Balázs Keszegh, and Mate Vizer
Vol. 0, no. 0, pp. 0-0, 0. Regular paper.
Abstract We prove that if an $n$-vertex graph $G$ can be drawn in the plane such that each pair of crossing edges is independent and there is a crossing-free edge that connects their endpoints, then $G$ has $O(n)$ edges. Graphs that admit such drawings are related to quasi-planar graphs and to maximal $1$-planar and fan-planar graphs.
Submitted: April 2017.
Reviewed: June 2017.
Revised: July 2017.
Accepted: July 2017.
Final: July 2017.
Appeared on-line: October 2017.