Journal of Graph Algorithms and Applications
|Home||Issues||About JGAA||Instructions for Authors|
Special Issue on Selected papers from the Twenty-third International Symposium on Graph Drawing and Network Visualization, GD 2015
Algorithms and Characterizations for 2-Layer Fan-planarity: From Caterpillar to Stegosaurus
Carla Binucci, Markus Chimani, Walter Didimo, Martin Gronemann, Karsten Klein, Jan Kratochvíl, Fabrizio Montecchiani, and Ioannis G. Tollis
Vol. 21, no. 1, pp. 81-102, 2017. Regular paper.
Abstract In a fan-planar drawing of a graph there is no edge that crosses two other independent edges. We study 2-layer fan-planar drawings, i.e., fan-planar drawings such that the vertices are restricted to two distinct horizontal layers and edges are straight-line segments that connect vertices of dierent layers. We characterize 2-layer fan-planar drawable graphs and describe a linear-time testing and embedding algorithm for biconnected graphs. We also study the relationship between 2-layer fan-planar graphs and 2-layer right-angle crossing graphs.
Submitted: November 2015.
Reviewed: February 2016.
Revised: May 2016.
Accepted: June 2016.
Final: July 2016.
Published: January 2017.