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.
Published In:
Proceedings of the 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015), Lecture Notes in Computer Science. 9411 Springer 2015, pp. 281-294.
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 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.
Download: |
![]() Download (441kB) |
---|---|
Editorial actions: | ![]() |
Item Type: | Proceedings article |
---|---|
Citations: | No citation data. |
Uncontrolled Keywords: | |
Subjects: |
|
Divisions: | Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger |
Related URLs: |
ZAIK Number: | UNSPECIFIED |
---|---|
Depositing User: | Martin Gronemann |
Date Deposited: | 12 Mar 2018 14:26 |
Last Modified: | 13 Mar 2018 09:36 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/925 |