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 Selected papers from the Twenty-seventh International Symposium on Graph Drawing and Network Visualization, GD 2019. The paper will receive a volume, an issue number, and page numbers when the whole special issue will be published.
Efficient Generation of Different Topological Representations of Graphs Beyond-Planarity
Vol. 0, no. 0, pp. 0-0, 0. Regular paper.
Abstract Beyond-planarity focuses on combinatorial properties of classes of non-planar graphs that allow for representations satisfying certain local geometric or topological constraints on their edge crossings. Beside the study of a specific graph class for its maximum edge density, another parameter that is often considered in the literature is the size of the largest complete or complete bipartite graph belonging to it. Overcoming the limitations of standard combinatorial arguments, we present a technique to systematically generate all non-isomorphic topological representations of complete and complete bipartite graphs, taking into account the constraints of the specific class. As a proof of concept, we apply our technique to various beyond-planarity classes and achieve new tight bounds for the aforementioned parameter.
Submitted: November 2019.
Reviewed: January 2020.
Revised: March 2020.
Accepted: April 2020.
Final: April 2020.
Appeared on-line: May 2020.