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.


Actions:
Download: [img] PDF - Preprinted Version
Download (441kB)
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Proceedings article
Citations: No citation data.
Uncontrolled Keywords:
Subjects:
  • 05-XX Combinatorics > 05Cxx Graph theory > 05C10 Planar graphs; geometric and topological aspects of graph theory

  • 05-XX Combinatorics > 05Cxx Graph theory > 05C62 Graph representations (geometric and intersection representations, etc.)

    		•
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
    Related URLs:
    Deposit Information:
    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