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.
A First Order Logic Definition of Beyond-Planar Graphs
Franz J. Brandenburg
Vol. 0, no. 0, pp. 0-0, 0. Regular paper.
Abstract Beyond-planarity is a collective term for classes of graphs that extend the planar graphs and are defined by drawings with restrictions on crossings. Examples are 1-planar, fan-planar, fan-crossing free, and quasi-planar graphs. We define these and other classes of beyond-planar graphs by simple first order formulas, using two predicates to express a crossing and an adjacency of two edges, and establish inclusion relationships between the so obtained graph classes.
Submitted: May 2017.
Reviewed: August 2017.
Revised: September 2017.
Accepted: October 2017.
Final: October 2017.
Appeared on-line: October 2017.