2-Layer Fan-Planarity: From Caterpillar to Stegosaurus

Binucci, Carla and Chimani, Markus and Didimo, Walter and Gronemann, Martin and Klein, Karsten and Kratochvíl, Jan and Montecchiani, Fabrizio and Tollis, Ioannis G. (2015) 2-Layer Fan-Planarity: From Caterpillar to Stegosaurus. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015 , pp. 281-294(Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_24).

Full text not available from this repository.


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 assigned to two distinct horizontal layers and edges are straight-line segments that connect vertices of different 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.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.770 Planarity Testing
P Styles > P.480 Layered
P Styles > P.540 Planar
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1496

Actions (login required)

View Item View Item